akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n, m; scanf("%d%d", &n, &m);
	std::vector<int> a(m), b(m), s(m);
	std::vector<std::vector<std::pair<int, i64>>> g(n);
	for(int i = 0; i < m; i++) {
		scanf("%d%d%d", &a[i], &b[i], &s[i]);

		a[i]--; b[i]--;
		g[a[i]].push_back({b[i], s[i]});
		g[b[i]].push_back({a[i], s[i]});
	}

	auto kiritan = [](auto & vec) {
		sort(begin(vec), end(vec));
		vec.erase(unique(begin(vec), end(vec)), end(vec));
	};
	auto powaaaa = [] {
		printf("0\n");
		std::exit(0);
	};

	i64 M = -1;
	std::queue<int> qu({0});
	std::vector<bool> used(n, false); used[0] = true;
	std::vector<std::vector<i64>> A(n), B(n); A[0].push_back(0);
	while(!qu.empty()) {
		auto v = qu.front(); qu.pop();

		used[v] = true;
		kiritan(A[v]);
		kiritan(B[v]);
		if(A[v].size() > 1 or B[v].size() > 1) powaaaa();
		if(A[v].size() and B[v].size()) {
			if((A[v][0] + B[v][0]) & 1) powaaaa();
			if(M == -1) M = (B[v][0] - A[v][0]) >> 1;
			if(M != (B[v][0] - A[v][0]) >> 1) powaaaa();
			if(M < 1) powaaaa();
		}
		for(auto e: g[v]) {
			int to = e.first;
			if(used[to]) continue;

			for(auto a: A[v]) B[to].push_back(e.second - a);
			for(auto b: B[v]) A[to].push_back(e.second - b);
			qu.push(to);
		}
	}
	
	i64 L = 1, R = 1LL << 60;
	for(int v = 0; v < n; v++) {
		for(auto a: A[v]) L = std::max(L, -a + 1);
		for(auto b: B[v]) R = std::min(R, b);
	}
	if(R <= L) powaaaa();
	if(M != -1) {
		if(L <= M and M < R) R = L + 1;
		else powaaaa();
	}
	printf("%d\n", R - L);
	return 0;
}


Measured memory_bytes: 24192
package main

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

func main() {
	N, M, X := ReadInt(), ReadInt(), ReadInt()
	C := make([]int, N)
	A := make([][]int, N)
	for i := 0; i < N; i++ {
		C[i] = ReadInt()
		A[i] = ReadInts(M)
	}
	const Inf = 1 << 62
	minCost := Inf
	for i := 0; i < 1<<N; i++ {
		cost := 0
		idx := 0
		levels := make([]int, M)
		for j := i; j > 0; j >>= 1 {
			if j&1 == 1 {
				cost += C[idx]
				for m, lvl := range A[idx] {
					levels[m] += lvl
				}
			}
			idx++
		}
		ok := true
		for i := 0; i < M; i++ {
			if levels[i] < X {
				ok = false
				break
			}
		}
		if ok && minCost > cost {
			minCost = cost
		}
	}

	if minCost == Inf {
		fmt.Println(-1)
	} else {
		fmt.Println(minCost)
	}
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 2240
import java.util.Scanner;

public class Main {
  public static void main(String... args) {
	Scanner sc = new Scanner(System.in);
	String a = sc.nextLine();
	int b = 0;
	for (int index = 0; index < a.length() ; index++) {
		char c = a.charAt(index);
		if (c == '1') {
			b = b + 1;
		}
	}
	System.out.println(b);
  }
}


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

int charToInt(char c){
    char zero_num = '0';
    return (int)c - (int)zero_num;
}

signed main(){
    int A,B,C;cin>>A>>B>>C;
    int K; cin>>K;

// A < B < C となればおｋ
    for(int i=0;i<K;i++){
        if(A>=B){
            B = B*2;
        }else if(B>=C){
            C = C*2;
        }else{
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    if(A<B && B<C){
            cout<<"Yes"<<endl;
            return 0;
    }
            cout<<"No"<<endl;



    return 0;
}

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

long gcd(long a,long b){return (a%b==0)?b:gcd(b,a%b);}
int main(){
  long i,N,M,p;
  cin>>N>>M;
  string s,t;
  cin>>s>>t;
  p=gcd(N,M);
  N/=p;M/=p;
  for(i=0;i<p;i++){
    if(s[i*N]!=t[i*M]){cout<<"-1"<<endl;return 0;}
  }
  cout<<N*M*p<<endl;
  return 0;
}


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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const ll MOD = 1000000007;

int main() {
  int h, w;
  cin >> h >> w;
  rep(i, h) {
    string s;
    cin >> s;
    rep(j, 2) cout << s << endl;
  }
}


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

#define F first 
#define S second
#define PB push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 10010, M = 1000010, mod = 1e9 + 7;

int n;
int a[N], f[M];
int primes[M], cnt;
bool st[M];

int qp(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = (LL)res * a % mod;
		a = (LL)a * a % mod;
		b >>= 1;
	}
	return res;
}

void init(int n)
{
	for (int i = 2; i <= n; i ++ )
	{
		if (!st[i]) primes[cnt ++ ] = i;
		for (int j = 0; primes[j] <= n / i; j ++ )
		{
			st[primes[j] * i] = true;
			if (i % primes[j] == 0) break;
		}
	}
}

int main()
{
	init(M - 1);
	
	cin >> n;
	for (int i = 0; i < n; i ++ )
	{
		cin >> a[i];
		
		int x = a[i];
		for (int i = 2; i <= x / i; i ++ )
			if (x % i == 0)
			{
				int cnt = 0;
				while (x % i == 0)
				{
					x /= i;
					cnt ++ ;
				}
				f[i] = max(f[i], cnt);
			}
		if (x > 1) f[x] = max(f[x], 1);
	}
	
	int s = 1;
	for (int i = 2; i < M; i ++ ) s = (LL)s * qp(i, f[i]) % mod;
	
	int res = 0;
	for (int i = 0; i < n; i ++ ) res = (res + (LL)s * qp(a[i], mod - 2) % mod) % mod;
	cout << res << endl;
    return 0;
}

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

constexpr int inf = 1e9;
constexpr ll linf = 1e18;

template <typename T>
class SegTree
{
public:
    SegTree(const int n, const T &unity) : _unity(unity)
    {
        _n = 1 << __lg(2 * n - 1);
        _data.resize(2 * _n, unity);
    }

    SegTree(const vector<T> &v, const T &unity) : _unity(unity)
    {
        int n = v.size();
        _n = 1 << __lg(2 * n - 1);
        _data.resize(2 * _n, unity);

        // 最下段に要素をセット
        for (int i = 0; i < n; i++) _data[i + n] = v[i];
        // セグメント木を構築
        for (int i = n - 1; i > 0; i--) _data[i] = f(_data[2 * i], _data[2 * i + 1]);
    }

    // k番目の値をxに更新する
    void update(int k, const T &x)
    {
        k += _n; // 葉の節点に変換
        _data[k] = x;
        while (k >>= 1) _data[k] = f(_data[2 * k], _data[2 * k + 1]);
    }

    // 区間[a, b)に対してクエリ処理した結果を返す
    T query(int a, int b)
    {
        T left = _unity, right = _unity;
        a += _n, b += _n; // 葉の節点に変換
        for (; a < b; a >>= 1, b >>= 1) {
            if (a & 1) left  = f(left, _data[a++]);
            if (b & 1) right = f(_data[--b], right);
        }
        return f(left, right);
    }

    const T &operator[](size_t i) const { return _data[i + _n]; }
    T &operator[](size_t i) { return _data[i + _n]; }

private:
    int _n;          // 要素数
    vector<T> _data; // データを格納する配列
    T _unity;        // 単位元

    // クエリ処理用の関数
    T f(const T &a, const T &b) { return min(a, b); }
};

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

    int n, q; cin >> n >> q;
    SegTree<int> rmq(n, numeric_limits<int>::max());

    while (q--) {
        int com, x, y; cin >> com >> x >> y;
        if (!com) rmq.update(x, y);
        else cout << rmq.query(x, y + 1) << '\n';
    }
    return 0;
}



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

int main(){
    int n,m;
    cin >> n >> m;
    
    int point[n];
    for(int i=1; i<=n; i++){
        point[i] = 0;
    }
    int exp[n];
    int target[m];
    for(int i=1; i<=m; i++){
        cin >> target[i];
    }
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            cin >> exp[j];
            if(target[i]==exp[j]){
                point[j]++;
            }
            if(target[i]!=j && exp[j]!=target[i]){
                point[target[i]]++;
            }
        }
    }
    
    for(int i=1; i<=n; i++){
        cout << point[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 3096
x, y = map(int, input().split())

l = []

if x <= y:
  l.append(y-x)
  
if -x <= y:
  l.append(y + x + 1)
  
if x <= -y:
  l.append(-y-x+1)
  
if -x <= -y:
  l.append(-y+x+2)
  
print(min(l))

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[] { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] { 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
	return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
	return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifdef EZZAT
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#else
#endif
}

const int N = 1 << 18, MID = 1 << 11, MAX = 1e5;
int dp[MID + 1][MAX + 1];
int val[N], w[N], h[N];
int main() {
	run();
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> val[i] >> w[i];
		h[i] = h[i >> 1] + 1;
	}
	for (int i = 1; i <= n && i <= MID; i++)
		for (int j = 0; j <= MAX; j++) {
			dp[i][j] = dp[i >> 1][j];
			if (j >= w[i])
				dp[i][j] = max(dp[i][j], dp[i >> 1][j - w[i]] + val[i]);
		}
	int q;
	cin >> q;
	while (q--) {
		int v, l;
		cin >> v >> l;
		vector<pair<int, int>> tmp;
		while (v > MID) {
			tmp.push_back( { val[v], w[v] });
			v >>= 1;
		}
		int rt = dp[v][l];
		for (int i = 1; i < (1 << sz(tmp)); i++) {
			int sumVal = 0, sumWig = 0;
			for (int j = 0; j < sz(tmp); j++) {
				if (i & (1 << j))
					sumWig += tmp[j].second, sumVal += tmp[j].first;
			}
			if (sumWig <= l)
				rt = max(rt, dp[v][l - sumWig] + sumVal);
		}
		cout << rt << endl;
	}
}


Measured memory_bytes: 806712
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0)
#define END return EXIT_SUCCESS
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR(I,0,N)
#define ALL(C) (C).begin(),(C).end()
#define INPUT(P) std::cin>>(P)
#define INPUT2(P1,P2) std::cin>>(P1)>>(P2)
#define INPUT3(P1,P2,P3) std::cin>>(P1)>>(P2)>>(P3)
#define INPUTS(I,N,V) REP(I,N) std::cin>>V[I]
#define OUTPUT(P) std::cout<<P<<std::endl
#define OUTPUT2(P1,P2) std::cout<<P1<<" "<<P2<<std::endl
#define OUTPUT3(P1,P2,P3) std::cout<<P1<<" "<<P2<<" "<<P3<<std::endl
#define OUTPUTS(I,N,V) REP(I,N) std::cout<<V[i]<<std::endl
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
using namespace std;
using namespace __gnu_pbds;
int i,j,k;
string S;
int K;
set<string> substrs;
int N;
int len;
inline void solve(){
  INPUT2(S,K);
  N=S.size();
  FOR(len,1,K+1){
    FOR(i,0,N-len+1){
      substrs.insert(S.substr(i,len));
    }
  }
  set<string>::iterator it=substrs.begin();
  advance(it,K-1);
  OUTPUT(*it);
}

int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 1664
A, B, C=map(int, input().split(" "))
mod=[]
pivot=1
step=1

while True:
  pivot = (step*A)%B
  if (step*A)%B==C:
    print('YES')
    #print('debug', step)
    break
  elif pivot in mod:
    print('NO')
    break
  else:
    mod.append(pivot)
    step=step+1

Measured memory_bytes: 8908
#include<iostream>
#include<string>

using namespace std;

const long long int MOD = 1000000007;
long long int dp[10005][105];
int d, n;
string s;

void reset()
{
    int i, val;

    for(i = 1;i <= n;i++)
    {
        for(val = 0;val < d;val++)
            dp[i][val] = 0;
    }

    for(val = 0;val <= 9;val++)
        dp[0][val % d] ++;
}

void solve()
{
    int i, j, val, dig;

    for(i = 1;i < n;i++)
    {
        for(val = 0;val < d;val++)
        {
            for(dig = 0;dig <= 9;dig++)
                dp[i][(val + dig) % d] = (dp[i][(val + dig) % d] + dp[i - 1][val]) % MOD;
        }
    }

    long long int ans = -1; // not counting 0
    int remain;
    val = 0;

    for(i = 0;i <= n - 2;i++)
    {
        for(j = 0;j <= (s[i] - '0') - 1; j++)
        {
            remain = (d - ((val + j) % d)) % d;
            ans = (ans + dp[n - i - 2][remain]) % MOD;
        }
        val = (val + (s[i] - '0')) % d;
    }

    for(j = 0;j <= (s[n - 1] - '0');j++)
    {
        remain = (d - ((val + j) % d)) % d;
        ans = (ans + ((val + j) % d == 0 ? 1 : 0)) % MOD;
    }

    cout<<ans<<"\n";
}

int main()
{
    cin>>s>>d;
    n = s.size();

    reset();
    solve();
    return 0;
}

Measured memory_bytes: 8448
#include <stdio.h>
int main(void){
  
  int n,i,j,res[7];
  double a;
  char b='*';
     
  res[1]=0;  
  res[2]=0;
  res[3]=0;
  res[4]=0;
  res[5]=0;
  res[6]=0;
  
  scanf("%d",&n);
  
  for(i=1;i<n+1;i++){
    
    scanf("%lf",&a);
    
    if( a < 165.0 ){
      res[1]=res[1]+1;
    }
    else if( a >= 165.0 && a < 170.0 ){
      res[2]=res[2]+1;
    }
    else if( a >= 170.0 && a < 175.0 ){
      res[3]=res[3]+1;
    }
    else if( a >= 175.0 && a < 180.0 ){
      res[4]=res[4]+1;
    }
    else if( a >= 180.0 && a < 185.0 ){
      res[5]=res[5]+1;
    }
    else{
      res[6]=res[6]+1;
    }
  }
  
  for( n=1 ; n<7 ; n++ ){
    
    printf("%d:",n);
    
    j=1;
    
    while( j < res[n]+1 ){
      
      printf("%c",b);
      j = j + 1;
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 0
import copy
import itertools

s = input()
q = int(input())
#s= list(input())

ct = 0
ls = []
rs = []
for i in range(q):
    qtmp = input().split()
    #qtmp = [2,1,'c']
    t = int(qtmp[0])
    if(t == 1):
        ct += 1
        ct = ct % 2
    else:
        f = int(qtmp[1])
        if(ct+1 == f):
            ls.append( qtmp[2])
        else:
            rs.append( qtmp[2])
if(ct == 1):
    tmp = rs
    rs = ls
    ls = tmp
    s = s[::-1]
for i in range(len(ls)):
    print(ls[len(ls)-i-1], end='')
print(s, end='')
for i in range(len(rs)):
    print(rs[i], end='')
print("")

Measured memory_bytes: 6916
#include<iostream>

using namespace std;

int MOD = 1e9+7;

long dp[112345][4];

string S;
int main () {
    cin >> S ;
    int N  = S.length();
    dp[0][0] = 1;
    for(int i=0;i<N;i++) {
            if(S[i] == '?') {
                for(int j=0;j<4;j++) (dp[i+1][j] = 3*dp[i][j]) %= MOD;
                for(int j=0;j<3;j++) (dp[i+1][j+1] += dp[i][j]) %= MOD;
            } else {
                for(int j=0;j<4;j++) dp[i+1][j] = dp[i][j];
                int c = S[i] - 'A';
                (dp[i+1][c+1] += dp[i][c]) %= MOD;
            }
    }
    cout << dp[N][3] << endl;
    return 0;
}

Measured memory_bytes: 3584
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const long long sss=1e14+5;
typedef struct node
{
    int adj;
    long long data;//adj为邻接点，data为边的权值
    struct node *next;
} node;

node *g[100005];
long long dis[100005];
int flag[100005],q[100005];//dis记录最短路径值，flag做出入队标记，q为队列
int n;
void spfa(int st)
{
    long long i,k,front,rear;
    node *p;
    for(i=1; i<=n; i++)
        dis[i]=sss;//初始化路径为长整型最大数
    memset(flag,0,sizeof(flag));//入队标记初始化为0
    front=0;
    rear=1;
    //将起始点入队
    dis[st]=0;//到自己距离为0
    q[rear]=st;//入队
    flag[st]=1;//置入队标记
    while(front!=rear)//当队列不为空时
    {
        front=(front+1)%100005;//出队，注意使用循环队列
        k=q[front];//记下出队点号
        flag[k]=0;//置出队标记
        p=g[k];//找到以出队点为头的邻接链表，考察由出队点中转至各邻接点路径是否更短
        while(p)
        {
            if(dis[k]+p->data<dis[p->adj])
            {
                dis[p->adj]=dis[k]+p->data;//路径更短，更新路径值
                if(!flag[p->adj])//若其邻接点未入队
                {
                    rear=(rear+1)%100005;//入队
                    q[rear]=p->adj;
                    flag[p->adj]=1;//*置入队标记
                }
            }
            p=p->next;/*记得改变循环变量，考察下一个邻接点*/
            //cout<<dis[k]<<endl;
        }
    }
}
int main()
{
    int i,x,y,q,k;
    long long z;
    node *p,*ss;
    scanf("%d",&n);//读入点数，边数
    memset(g,0,sizeof(g));//初始化图
    for(i=1; i<=n-1; i++) //读入边的信息，左点、右点、权值
    {
        scanf("%d%d%lld",&x,&y,&z);
        p=(node*)malloc(sizeof(node));//创建链表
        p->data=z;
        p->adj=y;
        p->next=g[x];//尾插法
        g[x]=p;
        ss=(node*)malloc(sizeof(node));//创建链表
        ss->data=z;
        ss->adj=x;
        ss->next=g[y];//尾插法
        g[y]=ss;
    }
    scanf("%d%d",&q,&k);
    spfa(k);//计算由起始点到各点的最短路径
    for(i=0;i<q;i++)
    {
        scanf("%d%d",&x,&y);
        //printf("%d %d\n",dis[x],dis[y]);
        printf("%lld\n",dis[x]+dis[y]);
    }
    return 0;
}

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

int main(void){
    long long int n = 0, k = 0, x = 0, oldx = 0, a = 0;

    scanf("%lld%lld", &n, &k);

    a = n / k;

    n = n - a*k;


    x = n;
    while(x != oldx){
        oldx = x;
        x = abs(x - k);
//        printf("x=%lld oldx=%lld\n", x, oldx);
        if(x > oldx){
            x = oldx;
            break;
        }
    }

    printf("%lld\n", x);

    return 0;

} 


Measured memory_bytes: 256
#include<bits/stdc++.h> 
#define LL long long
#define clr(x,i) memset(x,i,sizeof(x))
using namespace std;
const int N=200005;
int n,K,ban[11];
bool check(int x)
{
	for(int t=x;t;t/=10){
		if(ban[t%10]) return 0;
	}
	return 1;
}
int main()
{
	scanf("%d%d",&n,&K);
	for(int i=1;i<=K;i++){
		int x; scanf("%d",&x);
		ban[x]=1;
	}
	for(int i=n;i<=min(n*100,100000);i++){
		if(check(i)) { 
			printf("%d\n",i);break;
		}
	}
	return 0;
} 

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

int main(){

  int a,b,c;
  
  cin >> a >> b >> c;
  
  if(a + b == c || a + c == b || b + c == a){
    cout << "Yes";
  }else{
    cout << "No";
  }
    
    return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> x(N), y(N), z(N);
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i] >> z[i];
    }

    ll c1[] = { 1, 1, 1, 1, -1, -1, -1, -1 };
    ll c2[] = { 1, 1, -1, -1, 1, 1, -1, -1 };
    ll c3[] = { 1, -1, 1, -1, 1, -1, 1, -1 };

    ll ans = 0;

    for (int k = 0; k < 8; k++) {
        vector<vector<ll>> dp(N + 1, vector<ll>(M + 1, LLONG_MIN / 2));
        dp[0][0] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= M; j++) {
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
                if (j == M) {
                    continue;
                }
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + c1[k] * x[i] + c2[k] * y[i] + c3[k] * z[i]);
            }
        }

        ans = max(ans, dp[N][M]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 8192
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
    // Your code here!
    string S;
    cin >> S;
    long sum = 0;

    long N;
    N = S.length();

    for (long i = 0; i < pow(2, N - 1); i++)
    {
        long index = 1;
        long scale = 1;
        long tmp_sum = 0;
        for (long b = 0; b < N; b++)
        {
            tmp_sum += (S[(N - 1) - b] - '0') * scale;
            scale *= 10;

            if (i & index)
            {
                scale = 1;
            }

            index = index << 1;
        }

        sum += tmp_sum;
    }
    cout << sum;
}

Measured memory_bytes: 256
l=[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
]
n=int(input())
print(l[n-1])


Measured memory_bytes: 9068
X, N = map(int, input().split())

if N == 0:
    print(X)
    exit()

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

if X not in p:
    print(X)
    exit()
else:
    sa = 1
    while True:
        if X - sa not in p:
            print(X - sa)
            exit()
        elif X + sa not in p:
            print(X + sa)
            exit()
        sa += 1


Measured memory_bytes: 9192
import sys


class UnionFind:
    def __init__(self, node_size):
        self._node = node_size
        self.par = [i for i in range(self._node)]
        self.rank = [0] * self._node

    def find(self, ver):
        if self.par[ver] == ver:
            return ver
        else:
            self.par[ver] = self.find(self.par[ver])
            return self.par[ver]

    def unite(self, ver1, ver2):
        ver1, ver2 = self.find(ver1), self.find(ver2)
        if ver1 == ver2:
            return
        if self.rank[ver1] < self.rank[ver2]:
            ver1, ver2 = ver2, ver1
        self.par[ver2] = ver1
        if self.rank[ver1] == self.rank[ver2]:
            self.rank[ver1] += 1

    def same(self, ver1, ver2):
        return self.find(ver1) == self.find(ver2)


class Kruskal:

    class Edge:
        def __init__(self, u, v, cost):
            self.u, self.v, self.cost = u, v, cost

        def __lt__(self, another):
            return self.cost < another.cost

    def __init__(self, node_size):
        self._node = node_size
        self._edge_list = []

    def add_edge(self, u, v, cost):
        self._edge_list.append(self.Edge(u, v, cost))

    def solve(self):
        uf = UnionFind(self._node)
        res = 0
        edge_count = 0
        sorted_edge_list = sorted(self._edge_list)
        for e in sorted_edge_list:
            if not uf.same(e.u, e.v):
                uf.unite(e.u, e.v)
                res += e.cost
                edge_count += 1
                if edge_count == self._node-1:
                    break
        return res

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    kr = Kruskal(n)
    for _ in range(m):
        s, t, w = map(int, sys.stdin.readline().split())
        kr.add_edge(s, t, w)
    print(kr.solve())



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

using ll = long long;
static const ll MOD = 1e9 + 7;

// 組合せを素数で割った値を求める
// 今回は逆元を使うだけ
const int MAX = 1000007;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  
  vector<ll> a(n);
  for (int i = 0; i < n; i++) cin >> a.at(i);
  
  vector<int> x(1000005);
  for (int i = 0; i < n; i++) {
    ll now = a.at(i);
    for (int j = 2; j * j <= a.at(i); j++) {
      int count = 0;
      while (now % j == 0) {
        now /= j;
        count++;
      }
      x.at(j) = max(x.at(j), count);
    }
    if (now > 1) x.at(now) = max(x.at(now), 1);
  }
  
  ll keep = 1;
  for (int i = 2; i <= 1000000; i++) {
    keep *= pow(i, x.at(i));
    keep %= MOD;
  }
  
  COMinit();
  
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ans += keep * inv[a.at(i)];
    ans %= MOD;
  }
  
  cout << ans << '\n';
}

Measured memory_bytes: 27776
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cmath>
#include<bitset>
typedef long long ll;
#define PB	push_back
#define FOR(n)			for(int i = 0; i < n; ++i)
#define RFOR(n)			for(int i = n; i >= 0; --i)
#define FORR(start,end) for(int i = start; i < end; ++i)
#define COUT(n)			cout << n << " " << flush
#define vi(v)			vector<int> v
#define vii(v)			vector<pair<int,int>> v
#define mii(m)			map<int, int> m
#define msi(m)			map<string, int, less<>> m
#define mmsi(m)			multimap<string, int, less<>> m
#define mkp(a,b)		make_pair(a,b)
#define ALL(obj)		obj.begin(), obj.end()
#define PI 3.141592
#define MOD 1e9+7
using namespace std;

void solve() {
	ll n, a, b;
	cin >> n >> a >> b;
	if ((b - a) % 2 == 0)
		cout << (b - a) / 2 << endl;
	else
		cout << min(a - 1, n - b) + (b - a - 1) / 2 + 1 << endl;
}

int main() {
	solve();
	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>
#include <map>
using namespace std;

#define ll int64_t
const long MOD = 1e9 + 7;



int main()
{
  long n;
  string s;
  cin >> s;
  long a, b, c;
  a = (long)(s[0] - '0');
  b = (long)(s[1] - '0');
  c = (long)(s[2] - '0');
  // d = (long)(s[3]);

  vector<long> d(4);
  d[0] = a;
  d[1] = b;
  d[2] = c;
  d[3] = (long)(s[3] - '0');

  vector<bool> v(3, false);
  vector<bool> ans(3, false);

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

    long cc = d[0];
    for (int j = 0; j < 3; ++j) {
      if ( (i >> j) & 1 == 1  ) {
        cc += d[j + 1];
      } else {
        cc -= d[j + 1];
      }
    }
    cerr <<"i:" << ((i >> 0) & 1) <<endl;
    cerr <<"i:" << ((i >> 1)& 1 )<<endl;
    cerr <<"i:" << ((i >> 2) & 1 )<<endl;
    cerr <<"i:" << i << "   cc"<< cc <<endl;
    if (cc == 7) {
      for (int j = 0; j < 3; ++j) {
        if ((i >> j) & 1 == 1  )ans[j] = true;
      }
      break;
    }
    
  }


  cout << d[0];
  for (int i = 0; i < 3; ++i) {
    string s;
    if (ans[i] == true) {
      s = "+";
    } else {
      s = "-";
    }
    cout << s << d[i + 1];
  }

  cout  << "=7" << endl;


  return 0;



}

Measured memory_bytes: 256
from collections import Counter

n = int(input())
l = list(map(int, input().split()))

d1 = Counter(l[::2]).most_common()
d2 = Counter(l[1::2]).most_common()
d1.append([0,0])
d2.append([0,0])

if d1[0][0] != d2[0][0]:
    print(n//2-d1[0][1] + n//2-d2[0][1])
else:
    ans1 = n//2 - d1[0][1] + n//2 - d2[1][1]
    ans2 = n//2 - d1[1][1] + n//2 - d2[0][1]
    print(min(ans1, ans2))



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

int main() {
	int h,w,n;
	scanf("%d%d%d", &h, &w, &n);
	int arr[n];
	for (int i=0; i<n; i++) scanf("%d", &arr[i]);
	int grid[h][w];
	int cur=0;
	for (int i=0; i<h; i++) {
		if (i%2==0) {
			for (int j=0; j<w; j++) {
				if (arr[cur]==0) cur++;
				grid[i][j]=cur+1;
				arr[cur]--;
			}
		}
		else {
			for (int j=w-1; j>=0; j--) {
				if (arr[cur]==0) cur++;
				grid[i][j]=cur+1;
				arr[cur]--;
			}
		}
	}
	for (int i=0; i<h; i++) {
		for (int j=0; j<w; j++) {
			printf("%d%c", grid[i][j], j==w-1?'\n':' ');
		}
	}
}


Measured memory_bytes: 384
//#include <bits/stdint.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <bitset>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef long long LL;

typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const LL MOD = 1e9+7; 
const LL INF = 1LL << 60;
//vector <vector<int>> x(20, vector<int> (20)), y(20,vector<int> (20));
/*int counter_1 (int x) {
    if(x == 0) return 0;
    return counter_1(x >> 1) + (x & 1);
}*/
LL dp[100010];
const LL N=100010;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main() {
    int n;
    cin >> n;
    VI h(n);
    REP(i,n){
      cin >> h[i];
    }
    REP(i,n) dp[i] = MOD;
    dp[0]=0;
    for(int i=1; i<n; i++){
      chmin(dp[i], dp[i-1]+abs(h[i]-h[i-1]));
      if(i > 1) chmin(dp[i],dp[i-2]+abs(h[i]-h[i-2]));
    }
    cout << dp[n-1] << endl;
  }

Measured memory_bytes: 4576
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

int main() {
   int N, M, K, A;
   cin >> N >> M;
   map<int, int> log;
   for (int i = 0; i < N; i++) {
      cin >> K;
      for (int k = 0; k < K; k++) {
         cin >> A;
         log[A]++;
      }
   }

   int ans = 0;
   for (auto it = log.begin(); it != log.end(); ++it) {
      if (it->second == N) ans++;
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 256
N, A, B = map(int, input().split())
S = input()
a = 0
b = 0
for s in S:
    if s == 'a' and a+b < A+B:
        print('Yes')
        a += 1
    elif s == 'b' and a+b < A+B and b < B:
        print('Yes')
        b += 1
    else:
        print('No')


Measured memory_bytes: 53080
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


int main(){
    int A, B, K;
    cin >> A >> B >> K;    
    for(int i = 0; i < K; i++)
    {
        int tmp;
        if (i % 2 == 0){
            //A->B
            A -= A % 2;
            tmp = A / 2;
            A -= tmp;
            B += tmp;
        }else{
            //B->A
            B -= B % 2;
            tmp = B / 2;
            B -= tmp;
            A += tmp;
        }
    }    
    cout << A << " " << B << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rw freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
#define pb push_back
#define F first
#define S second
#define pf push_front
#define lp(i,a,b) for (int i=a;i<=(int)b;++i)
#define lp2(i,a,b) for (int i=a;i>=b;--i)
#define f(x) return cout<<x<<"\n",0
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define p(x) cout<<#x<<" = { "<<x<<" } \n"
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define EPS 1e-6
// to convert string to number use int a = stoi(string);
// to convert number to string use string s = to_string(int);
#define FAST ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define clr(c,x) memset(c,x,sizeof(c));
using namespace std;
const int N=2e5+5,mod=(int)1e9+7;
ll fast_pow(ll base,int power)
{
    if (!power)
        return 1;
    ll answer=fast_pow(base,power/2)%mod;
    answer*=answer;
    if (answer>=mod)
        answer%=mod;
    if (power&1)
        answer*=base;
    if (answer>=mod)
        answer%=mod;
    return answer;
}
ll fact[N]= {};
int main()
{
#ifdef ONLINE_JUDGE
    FAST;
#endif
    int r,c,rr,cc;
    cin>>r>>c>>rr>>cc;
    fact[0]=1;
    lp(i,1,2e5)
    {
        fact[i]=fact[i-1]*i;
        fact[i]%=mod;
    }
    ll fans=0;
    lp(i,1,r-rr)
    {
        int len=i+cc-2;
        int ch=i-1;
        ll dom=(fact[ch]*fact[len-ch])%mod;
        ll lef=((fact[len]*fast_pow(dom,mod-2))%mod);
        int hs=c-cc;
        int rs=r-i+1;
        len=rs+hs-2;
        ch=rs-1;
        dom=(fact[ch]*fact[len-ch])%mod;
        ll rig=((fact[len]*fast_pow(dom,mod-2))%mod);
        ll ans=lef*rig;
        ans%=mod;
        fans+=ans;
        fans%=mod;
    }
    cout<<fans<<"\n";
    return 0;
}


Measured memory_bytes: 1920
#include <iostream>

using namespace std;

int main() {
    int n,x,v[100005]={};
    
    cin>>n;
    
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        v[x]=i;
    }
    
    for(int i=1;i<=n;i++)
    {
        cout<<v[i]<<" "; 
    }
    
    return 0;
}

Measured memory_bytes: 1152
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const ll LINF = (ll)1 << 60;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
const long double PI=3.14159265358979323846264338327950;
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int e,y;
  cin>>e>>y;
  if(e==0){
    if(1868<=y && y<=1911){
      cout<<'M';
      cout<<y-1868+1<<'\n';
    }
    else if(1912<=y && y<=1925){
      cout<<'T';
      cout<<y-1912+1<<'\n';
    }
    else if(1926<=y && y<=1988){
      cout<<'S';
      cout<<y-1926+1<<'\n';
    }
    else if(1989<=y && y<=2016){
      cout<<'H';
      cout<<y-1989+1<<'\n';
    }
  }
  else if(e==1){
    cout<<1868+y-1<<'\n';
  }
  else if(e==2){
    cout<<1912+y-1<<'\n';
  }
  else if(e==3){
    cout<<1926+y-1<<'\n';
  }
  else if(e==4){
    cout<<1989+y-1<<'\n';
  }
  
  return(0);
}


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

const int inf = 1e9;
const ll linf = 1e18;

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

    int n; cin >> n;
    list<int> lst;
    for (int i = 0; i < n; i++) {
        int a; cin >> a; a--;
        lst.push_back(a);
    }

    auto itr = lst.begin();
    int now = 0;
    int crack = 0;
    while (itr != lst.end()) {
        if (*itr != now) {
            itr = lst.erase(itr);
            crack++;
        } else {
            now++;
            itr++;
        }
    }

    cout << ((lst.size() > 0) ? crack : -1) << endl;
    
    return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1<<30;

int main(){
  int a, b;cin>>a>>b;
  if(a+b==15)cout<<'+'<<endl;
  else if(a*b==15)cout<<'*'<<endl;
  else cout<<'x'<<endl;
}

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

namespace AtCoder
{

    static class Program
    {
        static void Main()
        {
            Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
            //

            int N = GetInt();
            int K = GetInt();
            var n = 1;
            for (int i = 0; i < N; i++)
            {
                n = Math.Min(2 * n, n + K);
            }
            var ans = n;

            Console.WriteLine(ans);

            //
            Console.Out.Flush();
            Console.ReadKey();
        }

        static void Solve()
        {

        }


        static public string GetStr() { return Console.ReadLine().Trim(); }
        static public int GetInt() { return int.Parse(Console.ReadLine()); }
        static public long GetLong() { return long.Parse(Console.ReadLine()); }
        static public string[] GetStrArray() { return Console.ReadLine().Split(' '); }
        static public int[] GetIntArray() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
        static public long[] GetLongArray() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
        static public char[] GetCharArray() { return Console.ReadLine().Split(' ').Select(char.Parse).ToArray(); }
        static public List<double> GetDoubleList() { return Console.ReadLine().Split(' ').Select(double.Parse).ToList(); }
        static public void WriteObjects<T>(IEnumerable<T> values) { foreach (var o in values) { Console.Write(o + " "); } }
        static string yesno(this bool b) { return b ? "yes" : "no"; }
        static string YesNo(this bool b) { return b ? "Yes" : "No"; }
        static string YESNO(this bool b) { return b ? "YES" : "NO"; }

        static bool eq<T, U>() => typeof(T).Equals(typeof(U));
        static T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
        static T cv<T>(string s) => eq<T, int>() ? ct<T, int>(int.Parse(s))
                           : eq<T, long>() ? ct<T, long>(long.Parse(s))
                           : eq<T, double>() ? ct<T, double>(double.Parse(s))
                           : eq<T, char>() ? ct<T, char>(s[0])
                                             : ct<T, string>(s);
        static void Multi<T>(out T a) => a = cv<T>(GetStr());
        static void Multi<T, U>(out T a, out U b)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]);
        }
        static void Multi<T, U, V>(out T a, out U b, out V c)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]);
        }
        static void Multi<T, U, V>(out T a, out U b, out V c, out V d)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<V>(ar[3]);
        }
    }
}

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

int main() {
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i < s.size() / 2; i++) {
        ans += s[i] != s[s.size() - 1 - i];
    }
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const ll INF=1234567890;

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

    vector<int> p(m);
    rep(i,m) cin >>p[i];
    sort(all(p),greater<int>());

    vector<int> c(n),e(n);
    rep(i,n) cin >>c[i] >>e[i];

    //?\????i?????\??????????????????????????±??????????????????????°????
    ll dp[10001];
    fill(dp,dp+10001,INF);
    dp[0]=0;

    rep(i,n)for(int j=m; j>=0; --j)
    {
        //??±i?????????
        int nx=j+c[i];
        if(nx>m) nx=m;
        dp[nx]=min(dp[nx],dp[j]+e[i]);
    }

    //????°?????????´??°????????????
    ll a=INF;
    for(int i=m; i>=0; --i)
    {
        a=min(a,dp[i]);
        dp[i]=min(dp[i],a);
    }

    //?\???????i????£???????????£????
    vector<ll> ben(m+1,0);
    for(int i=1; i<=m; ++i) ben[i]=ben[i-1]+p[i-1];

    ll ans=0;
    //?\???????i????£???????
    rep(i,m+1) ans=max(ans,ben[i]-dp[i]);

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

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

//const static double	de_PI	= 3.14159265358979323846;
//const static int	de_MOD	= 1000000007;
//const static int	de_MAX	= 999999999;
//const static int	de_MIN = -999999999;

int main(void) {

	//std::ifstream in("123.txt");	std::cin.rdbuf(in.rdbuf());

	std::string str;
	std::getline(std::cin, str);
	std::transform(str.begin(), str.end(), str.begin(), toupper);
	std::cout << str << std::endl;

}

Measured memory_bytes: 3196
#include <iostream>
#include <queue>
using namespace std;
int main(){
	int n, q;
	int left, mid, right;
	int cnt = 0;
	cin >> n;
	int A[n];
	for(int i = 0; i < n; i++){
		cin >> A[i];
	}
	cin >> q;
	int B[q];	
	for(int i = 0; i < q; i++){
		cin >> B[i];
		left = 0;
		right = n - 1;
		mid = (n-1)/2;
		while(left != right){
			if(left == right-1){
				if(B[i] == A[right] || B[i] == A[left])
					cnt++;
				break;
			}
			else if(B[i] == A[mid]){
				cnt++;
				break;
			}else if(B[i] > A[mid]){
				left = mid;
				mid = left + (right-left)/2;
			}else if(B[i] < A[mid]){
				right = mid;
				mid = left + (right-left)/2;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n; cin >> n;
  int x; cin >> x;
  vector<int> v(n);
  for(auto&e:v)cin >> e;
  sort(v.begin(),v.end());
  int cnt = n;
  for(auto e:v) x -= e;
  while(x - v.front() >= 0){
    x -= v.front();
    cnt++;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long N, x, result{};
    cin >> N >> x;
    vector<long long> a(N);
    for(long long i{}, tmp; i < N; ++i) {
        cin >> tmp;
        a[i] = tmp;
    }
    sort(begin(a), end(a));
    for(auto i: a){
        x-=i;
        if (x<0){break;}
        result++;
    }
    std::cout << (N==result && x > 0 ? result-1 : result) << std::endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int f(int x) {
    if(x == 1) return  300000;
    if(x == 2) return  200000;
    if(x == 3) return  100000;
    return 0;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int x, y;
    cin >> x >> y;

    int ans = f(x) + f(y);
    if(x == 1 && y == 1) ans += 400000;

    cout << ans << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>
 
typedef long long ll;
 
using namespace std;
 
int main() {
    int N, cnt = 0, i;
 
    cin >> N;
 
    for (i = 1; i <= N; i++) {
        if (i >= 10 && i <= 99) {
            continue;
        } else if (i >= 1000 && i <= 9999) {
            continue;
        } else if (i >= 100000 && i <= 999999) {
            continue;
        } 
 
        cnt++;
 
    }
 
    cout << cnt << endl;
 
    return 0;
}

Measured memory_bytes: 3580
// C - : (Colon)
#include <bits/stdc++.h>
using namespace std;
using LDBL = long double;

int main(){
	LDBL A,B,H,M; cin>>A>>B>>H>>M;
	LDBL h_deg, m_deg, deg, rad, c2;
	LDBL PI = acos(-1);
	// 時針:30度/1時間 0.5度/1分
	h_deg = H*30 + M*0.5; // H時M分後の時針の角度(deg)
	// 分針:6度/1分
	m_deg = M*6; // M分後の分針の角度(deg)
	deg = h_deg - m_deg;
	rad = deg * PI / 180;
	c2 = A*A + B*B - 2*A*B*cos(rad);
	cout<<setprecision(20)<<fixed<< sqrt(c2) <<endl;
}


Measured memory_bytes: 4176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;

int main(){
  vector<ll>a(5);
  for(int i=0; i<5; i++){
    cin >> a[i];
    if(a[i]==0)cout << i+1 << endl;
  }
  
  
  
}
  
  
  


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <cstdlib>
#include <math.h>

using namespace std;

typedef long long ll;
#define rep(i, n) for(long (i) = 0; (i) < (long) (n); (i)++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,a,b) for(long i=(a);i<(b);i++)
#define rrep1(i,a,b) for(long i=(a);i<=(b);i++)
#define rrrep(i,a,b) for(long i=(a);i>=(b);i--)
#define define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define X first
#define Y second
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int> >
#define vpl vector<pair<long, long> >
#define vppl vector<pair<long, pair<long, long> > >

const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const ll LINF = 1e18;

int printYes() {
    cout << "Yes" << endl;
    return 0;
}

int printNo() {
    cout << "No" << endl;
    return 0;
}

int ans;

int printAns() {
    cout << ans << endl;
    return 0;
}


int pow(int x) {
	if (x == 0) {
		return 1;
	}
	else {
		return pow(x - 1) * 2;
	}
}

int main(int argc, char const *argv[])
{
    string S;
    cin >> S;
    int ans = 0;
    rep(i,4) {
        string a = S.substr(i,1);
        if (a == "+") {
            ans++;
        } else
        {
            ans--;
        }
    }
    cout << ans << endl;
    
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;

int main(){
	ios::sync_with_stdio(false);
	string s;
	cin>>s;
	if(s.length()==3){
		reverse(s.begin(),s.end());
		cout<<s;
	}else cout<<s;
	return 0;
}

Measured memory_bytes: 256
N, X = map(int, input().split())
burger_size = 1
patty_size = [1]
for _ in range(N):
    burger_size = burger_size*2+3
    patty_size.append(patty_size[-1]*2+1)
i = -2
ans = 0
left = 1
right = burger_size
for i in range(N, -1, -1):
    m = (left+right)//2
    if i == 0:
        ans += 1
        break
    elif left == X:
        break
    elif right == X:
        ans += patty_size[i-1]*2+1
        break
    elif m == X:
        ans += patty_size[i-1]+1
        break
    elif left < X < m:
        left += 1
        right = m-1
    else:
        ans += patty_size[i-1]+1
        left = m+1
        right -= 1

print(ans)


Measured memory_bytes: 38448
#include <iostream>
#include <cstdlib>

using namespace std;

int main(){
  int x, a, b;
  cin >> x >> a >> b;
  if((a-b) >= 0) {
    cout << "delicious" << endl;
  } else if((a+x-b) >= 0) {
    cout << "safe" << endl;
  } else {
    cout << "dangerous" << endl;
  }
  return 0;
}


Measured memory_bytes: 3632
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 解説を参考に作成したソースコード
 */
public class Main {

	/** 大きい値の定義 */
	private static final int INF = Integer.MAX_VALUE >> 1;

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), ma = scanner.nextInt(), mb = scanner.nextInt();
			int[] a = new int[n], b = new int[n], c = new int[n];
			IntStream.range(0, n).forEach(i -> {
				a[i] = scanner.nextInt();
				b[i] = scanner.nextInt();
				c[i] = scanner.nextInt();
			});
			int result = getResult(n, ma, mb, 0, 0, 0, a, b, c, new HashMap<>());
			System.out.println((result < INF) ? result : -1);
		}
	}

	/**
	 * @param n
	 * @param ma
	 * @param mb
	 * @param now  現在計算しているindex
	 * @param nowA いままで使ったAの合計
	 * @param nowB いままで使ったBの合計
	 * @param a
	 * @param b
	 * @param c
	 * @param map  既に計算した結果を保存するマップ
	 * @return 計算結果
	 */
	private static int getResult(final int n, final int ma, final int mb, int now, int nowA, int nowB, final int[] a,
			final int[] b, final int[] c, final Map<List<Integer>, Integer> map) {
		if (now >= n) {
			return ((nowA > 0) && (nowB > 0) && (nowA * mb == nowB * ma)) ? 0 : INF;
		}
		List<Integer> key = Arrays.asList(now, nowA, nowB);
		Integer result = map.get(key);
		if (null == result) {
			result = Math.min(getResult(n, ma, mb, now + 1, nowA, nowB, a, b, c, map),
					getResult(n, ma, mb, now + 1, nowA + a[now], nowB + b[now], a, b, c, map) + c[now]);
			map.put(key, result);
		}
		return result;
	}
}


Measured memory_bytes: 135412