akhauriyash/Code-Regression huggingface dataset:
n,k=map(int,input().split())
a=list(map(int,input().split()))


mod=pow(10,9)+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
N = n
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

from collections import Counter
cnt_a=Counter(a)
list_a=list(cnt_a.keys())
list_a.sort()
num_a=len(list_a)
sa_=0
sa=[0]
for ai in list_a:
    sa_+=cnt_a[ai]
    sa.append(sa_)
ansmin=0
ansmax=0
for i in range(num_a):# list_a[i]がminになる場合の数
    k_=sa[num_a]-sa[i]
    if k_>=k:
        mi=0 if k_-cnt_a[list_a[i]]<k else cmb(k_-cnt_a[list_a[i]],k,mod)
        ansmin+=list_a[i]*(cmb(k_,k,mod)-mi)
        ansmin%=mod
for i in range(num_a):# list_a[i]がmaxになる場合の数
    k_=sa[i+1]
    if k_>=k:
        mi=0 if k_-cnt_a[list_a[i]]<k else cmb(k_-cnt_a[list_a[i]],k,mod)
        ansmax+=list_a[i]*(cmb(k_,k,mod)-mi)
        ansmax%=mod
print((ansmax-ansmin)%mod)


Measured memory_bytes: 29280
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll


signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n,m; cin >> n >> m;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }

    vector<ll> cnt(m * 2 + 1), val(m * 2 + 1);
    ll sum = 0;
    rep(i,0,n-1){
        ll s, t;
        s = a[i], t = a[i+1];
        if(s > t)t += m;

        sum += (t - s);

        if(t - s == 1)continue;
        cnt[s + 2]++;cnt[t + 1]--;
        val[t + 1] -= t - s - 1;
    }

    rep(i,0,m*2){
        cnt[i + 1] += cnt[i];
    }
   
    rep(i,1,m*2+1){
        val[i] += val[i-1] + cnt[i];
    }
  
    rep(i,m,2*m) val[i - m] += val[i];
    
    cout << sum - *max_element(all(val)) << endl;
}


Measured memory_bytes: 7088
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    if (n % 2 == 0) {
      System.out.println(n);
    } else {
      System.out.println(2*n);
    }

  }
}


Measured memory_bytes: 21332
s = gets.chomp
cA = s.slice!(0)
flagC = s[1..-2].include?("C")
if flagC = s[1..-2].include?("C") then
  cC = s[1..-2].index("C")
  s.slice!(cC+1)
end
oomoji = s.split("").any? do |c|
  c >= "A" && c <= "Z"
end
puts cA == "A" && flagC && !oomoji ? "AC" : "WA"


Measured memory_bytes: 1788
def judge(A, B, C, M):
	result = C
	for i in range(M):
		result += A[i] * B[i]

	return result > 0

def main():
	N, M, C = map(int, input().split())
	B = [int(x) for x in input().split()]
	count = 0

	for i in range(N):
		A = [int(x) for x in input().split()]

		if judge(A, B, C, M):
			count += 1

	print(count)



if __name__ == '__main__':
	main()

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

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

    int n=0,s=0,e=0,w=0;

    for(int i = 0; i < N.size(); i++){
     if(N[i] == 'N'){
     n++;
     }
     else if(N[i] == 'S'){
     s++;
     }
     else if(N[i] == 'E'){
     e++;
     }
     else{
     w++;
     }
    }

    bool can = true;


    if(n > 0  ){
        if(s == 0){
            can = false;
        }
    }


    if(s>0 ){
    if(n == 0){
        can = false;
    }
    }

    if(e > 0){
            if(w==0){
                can = false;
            }
    }

    if(w >0){
        if(e==0){
            can = false;
        }
    }

    if(can){
    cout << "Yes" << endl;
    }
    else{
    cout << "No" << endl;
    }
    return 0;
}


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

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))

int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}

const int N = 1e5 + 10;

int n, m;

VI edge[N];

int mxd[N], co[N];

void dfs(int u, int d, int c)
{
	if (d <= mxd[u]) return;
	if (!co[u]) co[u] = c;
	mxd[u] = d;
	for (auto v : edge[u]) dfs(v, d - 1, c);
}

int v[N], d[N], c[N];

int main()
{
	gii(n, m);
	for (int i = 1; i <= n; ++i) mxd[i] = -1;
	for (int i = 1; i <= m; ++i)
	{
		int u, v;
		gii(u, v);
		edge[u].pb(v);
		edge[v].pb(u);
	}
	int q;
	gi(q);
	for (int i = 1; i <= q; ++i)
		giii(v[i], d[i], c[i]);
	for (int i = q; i; --i)
		dfs(v[i], d[i], c[i]);
	for (int i = 1; i <= n; ++i)
		printf("%d\n", co[i]);
}

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

// 小数点以下桁数
// fixed << setprecision(i)

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

int main()
{
  int n, a, ans = 0;
  
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> a;
    while (a % 2 == 0)
    {
      ans++;
      a /= 2;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <queue>
#include <stack>
#include <string.h>
#include <list>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; i++)
#define repR(i,n) for(int i = n; i >= 0; i--)
#define FOR(i,m,n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main(){
    int n,t,a;
    cin >> n >> t >> a;
    int h[n];
    rep(i,n) cin >> h[i];
    int minv = INF, num = 0;
    rep(i,n){
        int temp = ((t*1000 - h[i]*6) - a*1000);
        if(temp < 0) temp = -temp;
        if(temp < minv){
            minv = temp;
            num = i+1;
        }
    }
    cout << num << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


X, K, D = MI()

if abs(X) >= K * D:
    print(abs(X) - K * D)
else:
    a = abs(abs(X) - (abs(X) // D) * D)
    K -= (abs(X) // D)
    if K % 2 == 0:
        print(a)
    else:
        print(abs(a - D))

Measured memory_bytes: 61660
#include <cstdio>

int N, M, P, S, X[101];

int main()
{
	while (true)
	{
		S = 0; scanf("%d%d%d", &N, &M, &P);

		if (N == 0) { break; }

		for (int i = 1; i <= N; i++) { scanf("%d", &X[i]); S += X[i]; }

		printf("%d\n", X[M] == 0 ? 0 : (100 - P) * S / X[M]);
	}

	return 0;
}

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

using namespace std;


#define MAXN 201
typedef long long ll;
const ll inf = 1e18;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll d[MAXN][MAXN];
  int n, m, r, R[MAXN];
  cin >> n >> m >> r;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      d[i][j] = inf;
      if (i==j) d[i][j] = 0;
    }
  }
  for (int i = 0; i < r; ++i) {
    cin >> R[i];
    R[i]--;
  }
  for (int i = 0; i < m; ++i) {
    int u, v;
    ll c;
    cin >> u >> v >> c;
    u--;
    v--;
    d[u][v] = c;
    d[v][u] = c;
  }
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
      }
    }
  }
  ll ans = inf;
  sort(R, R+r);
  do {
    ll sum = 0;
    for (int i = 0; i < r-1; ++i) {
      sum += d[R[i]][R[i+1]];
    }
    ans = min(ans, sum);
  } while (next_permutation(R, R+r));
  cout << ans << endl;
  return 0;
}


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

int main() {
	int n;
	string str;
	cin >> str;
	n = str.size();
	int a[10];
	for (int i = 0; i < n; i++) {
		a[i] = str[i] - '0';
	}
	long w = 0;
	for (long b = 0; b < 1 << (n - 1);b++) {
		long c = a[0];
		for (int i = 1; i < n;i++) {
			if (b >> (i - 1) & 1) {
				w += c;
				c = a[i];
			}
			else {
				c = c * 10 + a[i];
			}
		}
		w += c;
	}
	cout << w;
}

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

int main(){
 int n,min,max,a,i;
 long long sum=0;

 cin >> n;
  cin >> a ;
  min=a;
  max=a;
  sum=a;
 for(i=1;i<n;i++){
  cin >> a ;
  min=std::min(min,a);
  max=std::max(max,a);
  sum+=a;
 }

 cout << min << " " << max << " " << sum << endl;

 return 0;
}
 

Measured memory_bytes: 3112
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N,M = inputlist()
ans = [0]*(M+1)
c =0
for i in range(N):
    A = inputlist()
    K = A[0]
    Aa = A[1:]
    for j in range(K):
        ans[Aa[j]] +=1
for i in range(1,M+1):
    if ans[i] == N:
        c+=1
print(c)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
using ll = long long;
//二分探索かしゃくとり法
int main(){
    int n,m,k;
  	cin>>n>>m>>k;
    vector<int> a(n);
    vector<int> b(m);
    rep(i,n) cin>>a[i];
    rep(i,m) cin>>b[i];
    ll t=0;
    rep(i,m) t+=b[i];
    int j=m;
    int ans=0;
    rep(i,n+1){
        while(j>0 && t>k){
            --j;
            t-=b[j];
        }
        if(t>k) break;
        ans=max(ans,i+j);
        if(i==n)break;
        t+=a[i];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 4848
import java.util.*;
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 d = sc.nextInt();
        int ab = a + b;
        int cd = c + d;
        String ans = "";
        if (ab == cd) {
          ans = "Balanced";
        } else if (ab > cd) {
          ans = "Left";
        } else {
          ans = "Right";
        }
    
		// 出力
		System.out.println(ans);
	}
}


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

using namespace std;

int main() {
    int32_t n;
    int32_t m;
    std::cin >> n >> m;

    std::unordered_set<std::int32_t> us;

    for (int i= 0; i < m; i++)
    {
        int32_t t;
        std::cin >> t;
        for (int j = 0; j< t; j++)
        {
            int input;
            std::cin >> input;
            us.insert(input);
        }
        
    }

    std::cout << n - us.size() << std::endl;
    
    
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <string>
#include <numeric>

typedef long long ll;
using namespace std;

int main(){
    string w;
    cin >> w;
    int v[26] = {};
    for(auto c : w){
        v[c-'a']++;
    }
    for(auto a: v){
        if(a%2 != 0){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

  return 0; 
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
#include <sstream>
#include <bitset>
using namespace std;

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

ll euclidean_gcd(ll a, ll b)
{
    if(a<b) swap(a, b);
    ll r;
    while((r=a%b)!=0){
        a=b;
        b=r;
    }

    return b;
}

int main()
{
    ll a,b;
    cin >> a >> b;
    ll r=euclidean_gcd(a,b);
    cout << a*b/r << endl;

    

    return 0;
}

Measured memory_bytes: 256
import scala.io.{StdIn => in}
import scala.collection.{mutable => mu}

object Main extends App {
  val Array(n, m) = in.readLine.split(" ").map(_.toInt)

  val INF = 1 << 30
  val value = Array.fill(n)(INF)
  case class Edge(node:Int, cost:Int)
  val graph = Array.fill(n)(mu.ListBuffer.empty[Edge])

  Iterator.continually(in.readLine)
    .take(m)
    .map(_.split(" ").map(_.toInt))
    .foreach(e => {
      val l = e(0) - 1
      val r = e(1) - 1
      val d = e(2)
      graph(l) += new Edge(r, d)
      graph(r) += new Edge(l,-d)
    })

  def dfs(node:Int):Unit = {
    type Node = Int
    value(node) = 0
    val stk = mu.Stack.empty[Node]
    stk push node
    while(stk.nonEmpty) {
      val v = stk.pop
      if(graph(v).nonEmpty)
        graph(v).foreach( edge => {
          if(value(edge.node) == INF) {
            value(edge.node) = value(v) + edge.cost
            stk push edge.node
          }
        })
    }
  }

  (0 until n) foreach ( i => if(value(i) == INF) dfs(i) )

  val valid =
    (0 until n) forall ( i => {
      graph(i) forall ( edge => {
        value(i) + edge.cost == value(edge.node)
      })
    })

  val ans = if(valid) "Yes" else "No"
  println(ans)
}

Measured memory_bytes: 105624
import "dart:io";

void main() {
  int n = int.parse(stdin.readLineSync());
  List a1 = stdin.readLineSync().split(" ").map((x) => int.parse(x)).toList();
  List a2 = stdin.readLineSync().split(" ").map((x) => int.parse(x)).toList();
  int sum;
  sum = 0;
  List sumLists;
  sumLists = [];

  for (int i = 0; i < n; i++) {
    int sum1;
    sum1 = 0;
    int sum2;
    sum2 = 0;
    for (int j = 0; j <= i; j++) {
      sum1 = sum1 + a1[j];
    }
    for (int j = i; j < n; j++) {
      sum2 = sum2 + a2[j];
    }
    sum = sum1 + sum2;

    sumLists.add(sum);
  }
  List sortAi = sumLists..sort((b, a) => a.compareTo(b)); // 大きい順にsort
  print(sortAi[0]);
}

Measured memory_bytes: 13168
#include<bits/stdc++.h>
#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;
#define BEGIN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define END return EXIT_SUCCESS
#define rep(I,N) for(auto I=0;I<(N);++I)
#define up(I,A,B) for(auto I=(A);I<=(B);++I)
#define dw(I,A,B) for(auto I=(A);I>=(B);--I)
#define all(C) (C).begin(),(C).end()
#define rall(C) (C).rbegin(),(C).rend()
#define ft first
#define sd second
#define mp make_pair
#define mt make_tuple
#define pf push_front
#define pb push_back
#define pt pop_front
#define pk pop_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define rs resize
template<class T> T count_bit(T p){
  if(typeid(p)==typeid(int))return __builtin_popcount(p);
  else if(typeid(p)==typeid(long))return __builtin_popcountl(p);
  else return __builtin_popcountll(p);
}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T>inline void                                      in(T &p){cin>>p;}
template<class T1,class T2>inline void                            in(T1 &p1,T2 &p2){cin>>p1>>p2;}
template<class T1,class T2,class T3>inline void                   in(T1 &p1,T2 &p2,T3 &p3){cin>>p1>>p2>>p3;}
template<class T1,class T2,class T3,class T4>inline void          in(T1 &p1,T2 &p2,T3 &p3,T4 &p4){cin>>p1>>p2>>p3>>p4;}
template<class T1,class T2,class T3,class T4,class T5>inline void in(T1 &p1,T2 &p2,T3 &p3,T4 &p4,T5 &p5){cin>>p1>>p2>>p3>>p4>>p5;}
template<class T>inline void                                      ins(T &p){for_each(all(p),in<decltype(p[0])>);}
template<class T>inline void                             out(T p){cout<<p<<endl;}
template<class T1,class T2>inline void                   out(T1 p1,T2 p2){cout<<p1<<" "<<p2<<endl;}
template<class T1,class T2,class T3>inline void          out(T1 p1,T2 p2,T3 p3){cout<<p1<<" "<<p2<<" "<<p3<<endl;}
template<class T1,class T2,class T3,class T4>inline void out(T1 p1,T2 p2,T3 p3,T4 p4){cout<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<endl;}
inline                                              void out(double p){printf("%.10f\n",p);}
template<class T>inline                             void outs(T p){for_each(all(p),out<decltype(p[0])>);}

inline void solve(void){
  long r;
  in(r);
  out(3*r*r);
}
int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
//#include<stdlib.h>
using namespace std;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
 
    int n;
    cin>>n>>s;
    if(n<3200){
    	cout<<"red"<<endl;
    }
    else{
    	cout<<s<<endl;
    }

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	int N, K, S;
	cin >> N >> K >> S;
	if (S == mod-7) {
		for (int i = 0; i < K; i++) cout << S << " ";
		for (int i = 0; i < N - K; i++) cout << S - 1 << " ";
	}
	else {
		for (int i = 0; i < K; i++) cout << S << " ";
		for (int i = 0; i < N - K; i++) cout << S + 1 << " ";
	}
}

Measured memory_bytes: 1280
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = sum(b)
for i in range(1, n):
  if a[i-1] == a[i]-1:
    ans += c[a[i-1]-1]
    
print(ans)

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

using ll = long long;
#define ld long double
#define ull unsigned long long int

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  // (i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define ret return

typedef pair<int, int>    pii;
typedef vector<int>       vi;
typedef vector<vi>        vii;
typedef vector<long long> vl;

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

    // 入力
    int n;
    cin >> n;
    vi  l(n);
    int sum = 0, maxV = 0;
    rep(i, n) {
        cin >> l[i];
        sum += l[i];
        maxV = max(maxV, l[i]);
    }

    // 処理
    // 出力
    if (sum - maxV > maxV) {
        cout << "Yes" << endl;
    } else {
        cout << "No " << endl;
    }

    return 0;
}


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

int main( void )
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ans = 0;
    if ( a < b )
    {
        ans += a;
    }
    else
    {
        ans += b;
    }
    if ( c < d )
    {
        ans += c;
    }
    else
    {
        ans += d;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace::std;
#define int long long int
int n,m,dp[100005];

vector<int> v[100005],pre[100005],suf[100005];

void DFS1(int i,int p=0){
	dp[i]=1;
	for(auto a:v[i])
		if(a!=p){
			DFS1(a,i);
			dp[i]=dp[i]*(dp[a]+1)%m;
		}
}

void DFS2(int i,int p=0){
	for(int j=0;j<v[i].size();j++)
		pre[i][j]=(j?pre[i][j-1]:1)*(dp[v[i][j]]+1)%m
		,suf[i][v[i].size()-j-1]=(j?suf[i][v[i].size()-j]:1)*(dp[v[i][v[i].size()-j-1]]+1)%m;
	for(int j=0;j<v[i].size();j++)
		if(v[i][j]!=p){
			dp[i]=(j?pre[i][j-1]:1)*(j+1!=v[i].size()?suf[i][j+1]:1)%m;
			DFS2(v[i][j],i);
		}
	dp[i]=(v[i].size()?suf[i][0]:1);
}

main(){
	ios_base::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1,l,r;i<n;i++)
		cin>>l>>r,v[l].push_back(r),v[r].push_back(l),pre[l].push_back(0),suf[l].push_back(0),pre[r].push_back(0),suf[r].push_back(0);
	DFS1(1);
	DFS2(1);
	for(int i=1;i<=n;i++)
		cout<<dp[i]<<'\n';
}

Measured memory_bytes: 27916
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define scl(x) scanf("%lld", &x)
#define prnt(x) printf("%lld", x)
#define nl printf("\n")
#define white 0
#define red 1
#define blue -1
ll total=0,on=1;
vector<ll>number[4];
vector<ll>spc;
vector<ll>real_m;
vector< pair <ll,ll> > vect; 
ll zanisari[1009];
ll orac[100009];
vector<ll>zog;
vector<ll>biog;
vector<ll>graph[209];
map<ll,ll>color;
map<ll,ll>vis;
ll bipertite=1;
void dfs(ll src)
{
   if(color[src]==white)
   {
     color[src]=red;	
   }
   for(ll i=0;i<graph[src].size();i++)
   {
      ll v=graph[src][i];
      if(color[v]==white)
      {
         if(color[src]==red)
          color[v]=blue;
         else if(color[src]==blue)
           color[v]=red;
             dfs(v);   	
      }
      if(color[src]==color[v]){
         bipertite=-1;
         //return;
       }
        	
   }
  // return 1;	
}
int main()
{
    
  ll a,b,c,d,e,f,g,h=0,i,j,k,l=1,p=1,q,r=1,s,t,n,ans=1,cnt1=0,m,u,v=0,w,x;
  //const long long int fc=0,fc1=1,fc2=2;
  //sjkskjskjsklkslsklslksklsklsklskmllsk
  //scl(t);
  cin>>x;
  cout<<r-x;
 
     
      
      
      
      
      
      
  }





Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(x)    (x).begin(),(x).end()
typedef long long ll;
const int MOD = (int)1e9 + 7;

int main(){
  int n;
  cin >> n;
  for(int i=n;i<1000;i++) if(i % 111 == 0){
    cout << i << endl;
    break;
  }
}



Measured memory_bytes: 256
#include <stdio.h>

int calc(int w) {
  int mny = 1150;

  if (10 < w && w <= 20) {
    mny += 125 * (w - 10);
  }
  if (20 < w && w <= 30) {
    mny += 125 * 10;
    mny += 140 * (w - 20);
  }
  if (30 < w) {
    mny += 125 * 10;
    mny += 140 * 10;
    mny += 160 * (w - 30);
  }

  return mny;
}

int main() {
  int w, bm;

  bm = 4280;
  while (scanf("%d", &w) > 0) {
    if (w == -1) break;
    printf("%d\n", bm - calc(w));
  }

  return 0;
}

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

#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define rrep(i, a, b) for (int i = int(a) - 1; i >= b; i--)
#define sz(x) (int)(x).size()

using namespace std;
using ll = long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int main() {
  map<string, int> mp;
  ll n;
  cin >> n;
  rep(i, 0, n) {
    string s;
    cin >> s;
    mp[s] += 1;
  }
  int mx = 0;
  for (auto x : mp) {
    mx = max(x.second, mx);
  }
  vector<string> ans;
  for (auto x : mp) {
    if (mx == x.second) {
      ans.push_back(x.first);
    }
  }
  sort(ans.begin(), ans.end());

  rep(i, 0, sz(ans)) { cout << ans[i] << endl; }
}

Measured memory_bytes: 27504
#include<iostream>
using namespace std;
using ll = long long;

int main() {
	ll x, ans = 0;
	cin >> x;
	if (x > 11) { // x/11は5と6を繰り返したときの回数。
		ans = (x / 11) * 2; x %= 11;
	}
	if (x > 0) {//11以下のときの処理
		x -= 6; ans++;
	}
	if (x > 0) {
		x -= 5; ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		int n = int.Parse(Console.ReadLine());
    long[,] vertexes = new long[n,2];
    for(int i = 0; i < n; i++)
    {
      long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
      vertexes[i,0] = nums[0];
      vertexes[i,1] = nums[1];
    }
		int ansMemo = 0;
    bool answer = false;

    for(int i = 0; i < n; i++)
    {
      if(vertexes[i,0] == vertexes[i,1])
      {
        ansMemo++;
        if(ansMemo >= 3) answer = true;
      }else
      {
      ansMemo = 0;
      }
      
    }

		Console.WriteLine(answer?"Yes":"No");
	}
}

Measured memory_bytes: 27364
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <array>
#include <math.h>
#include <sstream>
typedef long long ll;
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    std::cin >> n;
    vector<int> l(n*2);
    for (int i = 0; i < n*2; i++) {
        std::cin >> l[i];
    }
    sort(l.begin(), l.end());
    int x = 0;
    for (int i = 0; i < n*2; i+=2) {
        x += min(l[i], l[i+1]);
    }
    std::cout << x << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct Node* NodePointer;

typedef struct Node {
  int key;
  NodePointer next, pre;
} Node;

NodePointer head, last;

NodePointer make_node(int key) {
  NodePointer tmp = malloc(sizeof(Node));
  tmp->next = tmp->pre = NULL;
  tmp->key = key;
  return tmp;
}

void init() {
  head = malloc(sizeof(Node));
  last = malloc(sizeof(Node));
  head->next = last;
  last->pre = head;
}

void insert(NodePointer s, int key) {
  NodePointer node = make_node(key);
  NodePointer t = s->next;
  s->next = node;
  node->pre = s;
  node->next = t;
  t->pre = node;
}

void delete(NodePointer p) {
  NodePointer s = p->pre;
  NodePointer t = p->next;
  s->next = t;
  t->pre = s;
  free(p);
}

int main() {
  int N, num;
  char str[30];
  NodePointer p;
  init();
  scanf(" %d ", &N);
  while(N--) {
    scanf(" %s ", str);
    if(!strcmp(str,"insert")) {
      scanf(" %d ", &num);
      insert(head,num);
    } else if(!strcmp(str,"delete")) {
      scanf(" %d ", &num);
      for(p = head->next; p != last; p = p->next) {
        if(p->key == num) {
          delete(p);
          break;
        }
      }
    } else if(!strcmp(str,"deleteFirst")) {
      delete(head->next);
    } else if(!strcmp(str,"deleteLast")) {
      delete(last->pre);
    }
  }

  for(p = head->next; p != last; p = p->next) {
    printf(p == head->next? "%d":" %d", p->key);
  }
  printf("\n");

  return 0;
}



Measured memory_bytes: 32984
/* Author : Alokit Kumar */
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
  int t,n,i,j,k,x,y,l,l1;k=1;
  cin>>x>>n;
  vector<int> v(n);
  for(i=0;i<n;i++) {cin>>v[i];if(v[i]==x) k=0;}
  sort(v.begin(),v.end());
  if(k)
  {
    cout<<x;
  }
  else
  {
    j=find(v.begin(),v.end(),x)-v.begin();
    for(i=j-1;i>=0;i--)
    {
      if(v[i]!=(x+i-j))
       break;
    }
    l=x+i-j;
    for(i=j+1;i<n;i++)
    {
      if(v[i]!=(x+i-j))
       break;
    }
    l1=x+i-j;
    
   if((x-l)<=(l1-x))
     cout<<l;
    else
     cout<<l1;
  }
}

Measured memory_bytes: 3624
from sys import stdin


def modpow(a, n, mod):
    """ 二分累乗法 """
    n_bin = bin(n)
    res = 1
    for i in range(len(n_bin)):
        res = res**2 % mod
        if n_bin[i] == '1':
            res = (res * a) % mod
    return res


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    MOD = 10**9 + 7
    ans =  pow(10, N, MOD)      # 全事象
    ans -=  pow(9, N, MOD) * 2  # 0の出ない確率+9の出ない確率
    ans +=  pow(8, N, MOD)      # 0かつ9の出ない確率
    ans %= MOD
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 61960
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int main(void) {
	int N; cin >> N;
	int k = 1;
	while(1) {
		if(k * 2 <= N) k *= 2;
		else break;
	}
	printf("%d\n", k);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<complex>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstdio>

using namespace std;

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

#define X real()
#define Y imag()
typedef complex<double> P;
typedef pair<P, P> L;
const double EPS = 1e-10;
int sig(double r) {return (r < -EPS) ? -1 : (r > EPS) ? 1: 0;}
bool eq(double a, double b) {return abs(a - b) < EPS;}
bool near(P a, P b) {return abs(b - a) < EPS;}
double dot(P a, P b) {return a.X * b.X + a.Y * b.Y;}
double cross(P a, P b) {return a.X * b.Y - a.Y * b.X;}
P vec(L a) {return a.second - a.first;}
enum CCW{FRONT = 1, RIGHT = 2, BACK = 4, LEFT = 8, ON = 16};
int ccw(L s, P p) {
  P a = vec(s);
  p -= s.first;
  double cr = cross(a, p);
  if (eq(cr, 0)) {
    if (sig(dot(a, p)) < 0) return BACK;
    if (sig(abs(a) - abs(p)) < 0) return FRONT;
    return ON;
  }
  return (cr > 0) ? LEFT : RIGHT;
}
bool iSS(L a, L b) {
  int cwaf = ccw(a, b.first);
  int cwbf = ccw(b, a.first);
  int cwas = ccw(a, b.second);
  int cwbs = ccw(b, a.second);
  return ((cwaf | cwas) & (cwbf | cwbs)) == (LEFT | RIGHT);
}
P pLL(L a, L b) {
  P va = vec(a);
  P vb = vec(b);
  return a.first + va * (cross(vb, b.first - a.first) / cross(vb, va));
}

vector<L> seg;
vector<P> p;

int main() {
  int n;
  for (;;) {
    cin >> n;
    if (n == 0) break;
    seg.clear();
    rep (i, n) {
      int xx, yy ,xxx, yyy;
      cin >> xx >> yy >> xxx >> yyy;
      seg.push_back(L(P(xx, yy), P(xxx, yyy)));
    }
    int res = 1;
    rep (i, n) {
      ++res;
      p.clear();
      for (int j = i + 1; j < n; ++j) {
	if (iSS(seg[i], seg[j])) {
	  P point = pLL(seg[i], seg[j]);
	  rep (k, p.size()) {
	    if (near(point, p[k])) goto aaa;
	  }
	  p.push_back(point);
	aaa:;
	}
      }
      res += p.size();
    }
    rep (i, p.size()) cout << p[i] << endl;
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 948
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
    int n, m, a, s=0,g[100][100] = { 0 }, v[100] = { 0 };
    scanf("%d%d", &n,&m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &a);
            g[i][j] = a;
        }
    }
    for (int i = 0; i < m;i++) {
        scanf("%d", &a);
        v[i] = a;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
             s+=g[i][j] * v[j];
        }
        printf("%d\n", s);
        s = 0;
    }
    return 0;
}


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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define MAX(a, b) ((a) < (b) ? (b) : (a))

const long long INF = 1LL << 60;
typedef unsigned long long ll;
const long long MOD = 1000000000 + 7;

int main()
{
    int n;
    cin >> n;
    map<string, int> mp;
    string s;
    rep(i, n)
    {
        cin >> s;
        sort(s.begin(), s.end());
        mp[s]++;
    }
    ll tmp;
    ll res = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++)
    {
        ll f = itr->second;
        tmp = f * (f - 1) / 2;
        res += tmp;
    }
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 11424
#include<iostream>
#include<bits/stdc++.h>
#include<string>
#include<vector>
using namespace std;
#define ll long long
void factorial(vector<ll>&f,ll n)
{
    for(ll i=1;i<=n;i++)
       f[i]=f[i-1]*i;
}
int main()
{
    ll n;
    cin>>n;
    vector<ll > v(n);
    vector<ll> a(n);
    for(ll i=0;i<n;i++)
     cin>>v[i];
     for(ll i=0;i<n;i++)
      cin>>a[i];
     vector<ll> f(n+1);
      f[0]=1;
     factorial(f,n);
     vector<ll>vs(n);
     vector<ll> as(n);
     vs[0]=0;
     as[0]=0;
     for(ll i=1;i<n;i++)
     {
         ll count=0;
         ll count1=0;
         for(ll j=0;j<i;j++)
          {
              if(v[j]<v[i])
              count++;
              if(a[j]<a[i])
              count1++;
          }
          vs[i]=count;
          as[i]=count1;
     }
     ll count=0,count1=0;
     for(ll i=0;i<n;i++)
      {
         count=count+(v[i]-vs[i]-1)*f[n-i-1];
         count1=count1+(a[i]-as[i]-1)*f[n-i-1];
      }
      cout<<abs(count-count1)<<endl;
       
    
     
    
     return 0;
    
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll;
template<class T>using vv = vector<vector<T>>; template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T>bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T>bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int N;
    cin >> N;
    vi d(N);
    rep(i, N) cin >> d[i];

    const int Max = 1e5 + 1;
    vi e(Max);
    rep(i, N) {
        e[d[i]]++;
    }
    vll accum(Max + 1);
    rep(i, Max) accum[i + 1] = accum[i] + e[i];

    auto l = lower_bound(all(accum), N / 2);
    if (*l == N / 2) {
        auto u = upper_bound(all(accum), N / 2);
        write(u - l);
    }
    else {
        write(0);
    }
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	vl v(n),p(n),q(n);
	rep(i,n)cin>>p[i];
	rep(i,n)cin>>q[i];
	iota(all(v),1ll);
	ll cur=0,a,b;
	do{
		cur++;
		if(v==p)a=cur;
		if(v==q)b=cur;
		//puta(v);
	}while(next_permutation(all(v)));
	puta(abs(a-b));
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> P;
int mod = 1e9+7;

vector<P> prime_factorize(int N){
	vector<P> ans;
	for(int a = 2; a*a <= N; a++){
		if(N%a == 0){
			int ex = 0;
			while(N%a == 0){
				ex++;
				N /= a;
			}
			ans.push_back(P(a, ex));
		}
	}
	if(N != 1) ans.push_back(P(N, 1));
	return ans;
}

signed main(){
	int N, Q; cin >> N >> Q;
	/*vector<P> map = prime_factorize(Q);
	int ans = 1;
	for(int i = 0; i < map.size(); i++){
        for(int j = 0; j < map[i].second/N; j++){
			 ans *= map[i].first;
		}
	} 
	cout << ans << endl;*/
	vector<P> pf = prime_factorize(Q);
    int res = 1;
    for (auto p : pf) {
        for (int j = 0; j < p.second/N; ++j) res *= p.first;
    }
    cout << res << endl;
}


Measured memory_bytes: 256
// finish date: 2018/01/20
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <map>
#include <climits>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long
#define bigmod 1000000007
#define INF 500000000


int main() {
    int N, M;
    cin >> N >> M;
    map<int, int> mp;
    int a, b;
    rep(i, M) {
        cin >> a >> b;
        a--;
        b--;
        mp[a]++;
        mp[b]++;
    }
    rep(i, N) cout << mp[i] << endl;


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  
  for(int i=0; i<N; i++){
    cin >> d.at(i); 
  }
  
  int temp;
  for(int i=0; i<N; i++){
    for(int j=i; j<N; j++){
        if( d.at(i) < d.at(j) ) {
          temp = d.at(i);
          d.at(i) = d.at(j);
          d.at(j) = temp;
        }
    }
  }
  
  int count = 1;
  for(int i=0; i<N-1; i++){
    if(d.at(i) > d.at(i+1))
      count++;
  }
  
  cout << count << endl;
}

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

#define rep(i,n) for(ll i = 0; i < n; i++)
#define REP(i,n) for(ll i = 1; i < n; i++)
#define sz(x) ll(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
using ll = long long;
using P = pair<ll,ll>;
using Pl = pair<ll,ll>;
using vi = vector<ll>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
const ll dx[] = {0,1,0,-1,1,1,-1,-1};
const ll dy[] = {1,0,-1,0,1,-1,-1,1};
const ll inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n, max_w;
  cin >> n >> max_w;
  vii value(4);
  ll a, b;
  cin >> a >> b;
  value[0].push_back(b);
  rep(i,n-1) {
    ll w, v;
    cin >> w >> v;
    value[w-a].push_back(v);
  }
  rep(i,4) sort(rall(value[i]));
  ll ans = 0;
  for(ll i = 0; i <= sz(value[0]); i++) {
    for(ll j = 0; j <= sz(value[1]); j++) {
      for(ll k = 0; k <= sz(value[2]); k++) {
        for(ll l = 0; l <= sz(value[3]); l++) {
          ll weight = i*a + j*(a+1) + k*(a+2) + l*(a+3);
          if(weight > max_w) continue;
          ll tmp = 0;
          rep(m,i) tmp += value[0][m];
          rep(m,j) tmp += value[1][m];
          rep(m,k) tmp += value[2][m];
          rep(m,l) tmp += value[3][m];
          chmax(ans, tmp);
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
from math import gcd
def lcm(i, j):
  return i * j // gcd(i, j)
def main():
  while True:
    n = int(input())
    if not n: break
    lst = [[]]
    weight = [-1 for i in range(n + 1)]
    def setWeight(n):
      p, q, r, b = lst[n]
      if weight[n] != -1: pass
      elif r == 0 and b == 0:
        weight[n] = (p + q) // gcd(p, q)
      elif r == 0:
        setWeight(b)
        l = lcm(weight[b] * q, p)
        weight[n] = l // q + l // p
      elif b == 0:
        setWeight(r)
        l = lcm(weight[r] * p, q)
        weight[n] = l // p + l // q
      else:
        if weight[r] == -1: setWeight(r)
        if weight[b] == -1: setWeight(b)
        l = lcm(weight[r] * p, weight[b]  * q)
        weight[n] = l // p + l // q
    for i in range(n):
      lst.append(list(map(int,input().split())))
    for i in range(0, n):
      if weight[i + 1] == -1:
        setWeight(i + 1)
    print(max(weight))

if __name__ == '__main__':
  main()


Measured memory_bytes: 5696
// lcmとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1001001001
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define double long double
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
using namespace std;
bool my_compare(pair<ll, ll> a, pair<ll , ll> b) {
    // 基本はfirstで比較
    if(a.first != b.first){
         return a.first < b.first; // 昇順
        //return a.first > b.first; // 降順
    }

    // それ以外はsecondで比較
    if(a.second != b.second){
        return a.second > b.second;
    }else{
        // どちらも同じ
        return true;
    }
}

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

    ll a,b,m,n,maxi=0,f=0,mini=INF,sum=0;
    string str,sub;
    ll h,w;
    string str1;
    ll v[3][3];
    ll mx[3]={0,0,0};
    rep(i,3)rep(j,3) cin>>v[i][j];
    rep(i,3){
        ll tmp=120;
        rep(j,3){
            tmp=min(v[i][j],tmp);
        }
        mx[i]=tmp;
    }
    rep(i,3){
        rep(j,3){
            v[i][j]-=mx[i];
           // cout<<v[i][j]<<" ";
        }
       // cout<<endl;
    }
    f=1;
    rep(i,3){
        
        if(v[0][i]!=v[1][i]||v[1][i]!=v[2][i]) f=0;
        
    }
    if(f==1) Yes;
    else No;


    return 0;
}


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

int main(){
  double a,b,c,d,e,f,answer1,answer2;
  while(cin >> a>>b>>c>>d>>e>>f){
    answer1=(e*c-b*f)/(e*a-b*d);
    answer2=(c*d-a*f)/(d*b-a*e);
    if(answer1==-0.000){
      answer1=0.000;
    }
      if(answer2==-0.000){
      answer1=0.000;
    }
    
    cout << fixed << setprecision(3) << answer1<<" "<<answer2 << endl; 
  }

    return 0;
}


Measured memory_bytes: 3204
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <ctime>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <memory.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long double LD;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL
#define DEBUG(x) { cerr << "# " << #x << ": " << x << endl;}
#else
#define DEBUG(x)
#endif
mt19937_64 mt(time(0));
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/
const int MAXN = 2e5 + 10;
int k[MAXN], a[MAXN], b[MAXN], idx[MAXN];

bool cmp(int i, int j) {
  return k[i] < k[j];
}


int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cout.precision(10); cout << fixed;
#ifdef LOCAL
  freopen("../test.txt", "r", stdin);
    // freopen("../output.txt", "w", stdout);
#endif
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    LL ret = 0;
    vector<int> idx[2];
    for (int i = 0; i < n; i++) {
      cin >> k[i] >> a[i] >> b[i];
      LL tmp = min(a[i], b[i]);
      ret += tmp;
      a[i] -= tmp;
      b[i] -= tmp;
      if (a[i] > b[i]) idx[0].push_back(i);
      else if (b[i] > a[i]) idx[1].push_back(i);
    }
    {
      sort(idx[0].begin(), idx[0].end(), cmp);
      priority_queue<int, vector<int>, greater<int>> pq;
      for (int i : idx[0]) {
        if (pq.size() < k[i]) {
          pq.push(a[i]);
          ret += a[i];
        }
        else {
          if (pq.top() < a[i]) {
            ret -= pq.top();
            pq.pop();
            pq.push(a[i]);
            ret += a[i];
          }
        }
      }
    }
    {
      sort(idx[1].begin(), idx[1].end(), cmp);
      reverse(idx[1].begin(), idx[1].end());
      priority_queue<int, vector<int>, greater<int>> pq;
      for (int i : idx[1]) {
        int tmp = n - k[i];
        if (tmp == 0) continue;
        if (pq.size() < tmp) {
          ret += b[i];
          pq.push(b[i]);
        } else if (pq.top() < b[i]) {
          ret -= pq.top();
          pq.pop();
          ret += b[i];
          pq.push(b[i]);
        }
      }
    }
    cout << ret << '\n';
  }






/*---------------------------------------Coding Space End------------------------------------------*/
#ifdef LOCAL
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
  return 0;
}
/* author:  txingml */
/* picture is from hamayanhamayan(CF handle) */


Measured memory_bytes: 6784
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <iomanip>
#include <map>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    vector<int> m;
    for(int i=1;i<n;i++){
        if(s[i-1]=='A'&&s[i]=='C'){
            m.push_back(i-1);
        }
    }
    
    int ans[100010];
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        auto ans1=lower_bound(m.begin(),m.end(), l-1);
        auto ans2=lower_bound(m.begin(),m.end(), r-1);
        ans[i]=ans2-ans1;
    }
    
    for(int i=0;i<q;i++) cout<<ans[i]<<endl;
}

Measured memory_bytes: 1612
#include <iostream>
#include<algorithm>
#include<vector>
#include<string>

using namespace std;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}


string s;
int x,y;
vector<int> xl,yl;
vector<vector<bool>> dpx,dpy;

int main(){
    cin>>s>>x>>y;
    int n=s.length();
    
    int cnt=0;
    bool check=0; //dx,dy
    for (int i=0;i<n;i++){
        if (s[i]=='T'){
            if (check==0){
                xl.push_back(cnt);
            } else {
                yl.push_back(cnt);
            }
            cnt=0;
            check=!check;
        }
        else{
            cnt+=1;
        }
        
    }
    if (cnt!=0){
        if (check){
            yl.push_back(cnt);
        } else{
            xl.push_back(cnt);
        }
    }
    dpx.assign(xl.size()+1,vector<bool>(2*n+1,false));
    dpx[1][n+xl[0]]=true;
    for (int i=1;i<xl.size();i++){
        for (int j=0;j<2*n+1;j++){
            if (dpx[i][j]==true) {
                dpx[i+1][j+xl[i]]=true;
                dpx[i+1][j-xl[i]]=true;
            }
        }
    }
    dpy.assign(yl.size()+1,vector<bool>(2*n+1,false));
    dpy[0][n]=true;
    for (int i=0;i<yl.size();i++){
        for (int j=0;j<2*n+1;j++){
            if (dpy[i][j]==true){
                dpy[i+1][j+yl[i]]=true;
                dpy[i+1][j-yl[i]]=true;
            }
        }
    }
    if (dpx[xl.size()][x+n]==true && dpy[yl.size()][y+n]==true){
        printf("Yes\n");
    }else{
     printf("No\n");
    }
    //cout<<s<<x<<y<<endl;
    //cout<<xl<<dpx<<endl;
}

Measured memory_bytes: 16128
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main(){
    string s;
    cin >> s;
    int c=0;
    int f=0;
    for(int i=0;i<s.length();i++){
        if(s.at(i)=='C')c++;
        if(s.at(i)=='F'&&c>0)f++;
    }
    cout << (f > 0 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256