akhauriyash/Code-Regression huggingface dataset:
// template version 1.15
using namespace std;
#include <bits/stdc++.h>

// varibable settings
#define int long long
const int INF=1e18;

// define basic macro {{{
#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<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(a, b, c) make_tuple(a, b, c)
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

#define divceil(a,b) ((a)+(b)-1)/(b)
#define is_in(x, a, b) ((a)<=(x) && (x)<(b))
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define slice(l, r) substr(l, r-l)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
#else
    #define dump(...) 42
    #define dump_1d(...) 42
    #define dump_2d(...) 42
    #define cerrendl 42
#endif
//}}}

// template<class T> vector<vector<vector<T>>> make_vector_2d(int n1, int n2, T init_value){
//     return vector<vector<T>>(n1, vector<T>(n2, init_value));
// }
//
// template<class T> vector<vector<vector<T>>> make_vector_3d(int n1, int n2, int n3, T init_value){
//     return vector<vector<vector<T>>>(n1, vector<vector<T>>(n2, vector<T>(n3, init_value)));
// }
//

template<class T>
void pairsort(vector<T>& x, vector<T>& y){
    int n = sz(x);
    vector<tuple<T, T>> t(n);
    rep(i, n){
        t[i] = make_tuple(x[i], y[i]);
    }
    sort(all(t), greater<>());
    rep(i, n){
        x[i] = get<0>(t[i]);
        y[i] = get<1>(t[i]);
    }
}

signed main() {
    int n;cin>>n;
    vector<int> a(n);
    vector<int> idx(n);
    rep(i, n) {
        cin>>a[i];
        idx[i] = i;
    }
    pairsort(a, idx);
    dump(a);
    dump(idx);

    vvi dp(n+1, vi(n+1, -INF));
    dp[0][0] = 0;

    rep(i, n){
        // kubaru
        rep(l, 0, n+1){
            // 左に寄せる
            if (l+1<=n) chmax(dp[i+1][l+1], dp[i][l] + a[i]*abs((idx[i]+1) - (l+1)));

            // 右に寄せる
            int y = idx[i]+1;
            int r = n + (l - i);
            dump(i, l, y, r, a[i], abs((r-1) - y + 1));
            chmax(dp[i+1][l  ], dp[i][l] + a[i]*abs((r-1) - y + 1));
        }
    }
    dump_2d(dp, n+1, n+1);

    int ans = -INF;
    rep(l, n+1) chmax(ans, dp[n][l]);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 34616
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);std::iostream::sync_with_stdio(0);cout<<std::fixed<<std::setprecision(10);cerr<<std::fixed<<std::setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}

const int N=228;
string s[N];
int c[N],q[N];
int n;
void ch(int v,int cc=1){
    c[v]=cc;
    forn(i,n){
        if(s[v][i]=='1'){
            if(!c[i])ch(i,3-cc);
            if(c[i]==c[v]){
                cout<<"-1\n";
                exit(0);
            }
        }
    }
}
int bfs(int z){
    c[z]=1;
    int l=0,r=0;
    q[r++]=z;
    int res=1;
    while(l<r){
        int v=q[l++];
        upx(res,c[v]);
        forn(i,n){
            if(s[v][i]=='1'&&!c[i]){
                q[r++]=i;
                c[i]=c[v]+1;
            }
        }
    }
    return res;
}
int32_t main(){
    cin>>n;
    forn(i,n)cin>>s[i];
    ch(1);
    int ans=1;
    forn(i,n){
        memset(c,0,sizeof c);
        upx(ans,bfs(i));
    }
    cout<<ans<<'\n';
    return 0;
}


Measured memory_bytes: 384
import scala.math

object Main {
	def main(args: Array[String]) {
		val input = io.Source.stdin.getLines().mkString("\n")
		println(solve(input).trim)
	}

	def solve(input: String): String = {
		 val a = input.toInt
		 val ans = a * 2 * math.Pi
		 ans.toString
	}

}

Measured memory_bytes: 54876
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] t = new int[n];
        int sum = 0;

        for (int i = 0; i < n; i++) {
            t[i] = sc.nextInt();
            sum += t[i];
        }

        int m = sc.nextInt();

        for (int i = 0; i < m; i++) {
            int p = sc.nextInt() - 1;
            int x = sc.nextInt();
            System.out.println(sum - t[p] + x);
        }

        sc.close();
    }
}

Measured memory_bytes: 22740
#include <iostream>
#include <map>
using namespace std;
#define vi vector<int>
#define msi map<string, int>


int main(){
  ios_base::sync_with_stdio(false);
  msi table;
  int n;
  cin>>n;
  while(n--){
    string s;
    cin>>s;
    table[s] += 1;
   }
   int ans = table.size(); 
   cout<<ans<<endl;
}

Measured memory_bytes: 18848
object Main{
  def main(args: Array[String]) {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt
    val list = Seq.fill(n)(sc.nextInt)

    val (alice, bob) = list.
      sorted(Ordering[Int].reverse).
      zipWithIndex.
      foldLeft{ (Seq.empty[Int], Seq.empty[Int]) } {
        case ((alice, bob), (a, i)) => i match {
          case i if i % 2 == 0 => (alice :+ a, bob)
          case _ => (alice, bob :+ a)
        }
      }
    println(sum(alice) - sum(bob))

    def sum(xs: Seq[Int]): Int = xs.foldLeft(0)(_ + _)
  }
}

Measured memory_bytes: 25672
#pragma GCC optimize("Ofast",3,"inline")
#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define m_p make_pair
#define y1 ygftgfgcdtfgxffgx
#define y2 yfdsesgvtyghftfvv
#define x1 xvyr6cf6fgcfgf676
#define x2 xcr6rfc5r66y6r6fr
#define up_bound upper_bound
#define low_bound lower_bound
#define next_per next_permutation
#define pb push_back
#define i_to_s to_string
typedef priority_queue<int> p_queue;
typedef priority_queue<int, vector<int>, greater<int> > min_p_queue;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int mon[20]={31,28,31,30,31,30,31,31,30,31,30,31};
ll gcd(ll x,ll y){return ((y==0)?x:gcd(y,x%y));}
ll a,b,c;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>a>>b>>c;
	ll ans=0;
	ll p=min(b-1,c);
	ans=p*a/b;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 3648
import java.math.BigDecimal;
import java.util.*;

public class Main {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        long N = sc.nextLong(); // s
        long M = sc.nextLong(); // c

        long sccCount = M / 2; // scc max

        if (N < sccCount) {
            System.out.println((M - (2 * N)) / 4 + N);
        } else {
            System.out.println(sccCount);
        }
    }
}

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



int main() {
  ll N;
  cin >>N;
  string S;
  string ans = "Three";
  rep (i,N)
  {
    cin >> S;
    if (S == "Y")
    {
      ans = "Four";
      break;
    }
  }
  cout << ans << endl;
      
    
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
#include<algorithm>
#include<cmath>
#include<set>
#include<vector>
#define mod 1000000007
#define int long long int
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,k;
	cin>>n>>k;
	int arr[n+1];
	int j;
	for(j=1;j<=n;j++)
	  cin>>arr[j];
	int val=1;
	if(k<=1000000)
	{
		while(k!=0)
		{
			val=arr[val];
			k--;
		}
		cout<<val<<endl;
	}
	else
	{
		bool visited[n+1]={false};
		visited[1]=true;
		int src=1;
		if(arr[1]==1)
	    {
			cout<<1<<endl;
			exit(0);
		}
		set<int> st;
		while(1)
		{
			auto it=st.find(src);
			if(it!=st.end())
			{
				int moves=1;
				int val=src;
				int val2=arr[src];
				while(val2!=val)
				{
					val2=arr[val2];
					moves++;
				}
				k=k%moves;
				while(k!=0)
				{
					k--;
					src=arr[src];
				}
				cout<<src<<endl;
				exit(0);
			}
			else
			{
				st.insert(src);
				k--;
				src=arr[src];
			}
		}
	}
	
}


Measured memory_bytes: 12876
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
//#include <string>
using namespace std;

int main()
{
	int i,n,k,h[200000],c=0;
	cin>>n;
	cin>>k;
	for(i=0;i<n;i++)
	{
		cin>>h[i];
		if(h[i]>=k)
			c++;
	}
	
	cout<<c;
	return 0;
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vint;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef vector<string> vstr;
typedef vector<vector<int>> vvint;
typedef vector<pair<int, int>> vpii;
typedef vector<pair<ll, ll>> vpll;
typedef priority_queue<int, vector<int>, greater<int>> spqint; //小さい順に取り出し
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;     //小さい順に取り出し
typedef priority_queue<int, vector<int>, less<int>> bpqint;    //大きい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;        //大きい順に取り出し

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (int)a; i < (int)b; i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); i++)
#define FI first
#define SE second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define TS to_string
#define BS binary_search
#define LB lower_bound
#define UB upper_bound
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) (ll) x.size()
#define SP(x) setprecision((ll)x)

int INF = 1e9;
int NIL = -1;
ll MOD = 1000000007;
ll LINF = 1e18;
double EPS = 1e-9;
double PI = M_PI;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }     //最小公倍数

void yes(){ cout << "Yes" << endl;}
void no(){ cout << "No" << endl;}
//-----------------------------------------

//-----------------------------------------
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::chrono::system_clock::time_point start,end;
    start = std::chrono::system_clock::now();

    int h, w ;
    cin >> h >> w ;
    vector<int> cnt(26,0) ;
    REP(i,h){
        string s ;
        cin >> s ;
        REP(j,w){
            cnt[s[j]-'a']++; 
        }
    }
    vector<int> cnt4(4,0) ;
    REP(i,26){
        cnt4[cnt[i]%4]++ ;
    }
    if(h%2==0 && w%2==0){
        if(cnt4[1]==0 && cnt4[2]==0 && cnt4[3]==0){
            yes() ;
        }
        else{
            no() ;
        }
    }
    else if(h*w%2==0){
        if(h%2==0){
            w = h ;
        }
        if(cnt4[1]==0 && cnt4[3]==0 && cnt4[2]<=w/2){
            yes() ;
        }
        else{
            no() ;
        }
    }
    else{
        if(cnt4[1]+cnt4[3]>=2){
            no() ;
        }
        else{
            if(cnt4[1]==1){
                if(cnt4[2]<=(w+h)/2-1){
                    yes() ;
                }
                else{
                    no() ;
                }
            }
            else{
                if(cnt4[2]<=(w+h)/2-2){
                    yes() ;
                }
                else{
                    no() ;
                }
            }
        }
    }


    end = std::chrono::system_clock::now();
    auto elapsed = std::chrono::duration_cast< std::chrono::milliseconds >(end - start).count();
    //std::cout << elapsed <<"ms"<< std::endl;

    

    return 0;
}



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

int main(){
  char str1[3];
  char str2[3];
  cin >> str1 >> str2;
  if(str1[0]==str2[2] && str1[1]==str2[1] && str1[2]==str2[0]){
    cout << "YES" << endl;
  }else{
    cout <<"NO" << endl;
  }
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

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

	int N, M;
	cin >> N >> M;
	vector<double> A(N);
	double sum = 0;
	rep(i, 0, N)
	{
		cin >> A[i];
		sum += A[i];
	}
	sum /= (4 * M);
	int cnt = 0;
	rep(i, 0, N)
	{
		if (A[i] > sum - EPS)
		{
			cnt++;
		}
	}

	if (cnt >= M)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i]; 
  }
}

static void printArray(int A[], int num, int q) {
  for (int i = 0; i < num; i++) {
    cout << (i != 0 ? " " : "");
    if (i != q) {
      cout << A[i];
    } else {
      cout << '[' << A[i] << ']';
    }
  }
  cout << endl; 
}

static int partition(int A[], int p, int r) {
  int x = A[r];
  int i = p - 1;
  for (int j = p; j < r; j++) {
    if (A[j] <= x) {
      i++;
      swap(A[i], A[j]);
    }
  }
  swap(A[i + 1], A[r]);
  return i + 1; 
}

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

  vector<int> A(n);
  inputArray(&A[0], n);
  
  int q = partition(&A[0], 0, n - 1);
  printArray(&A[0], n, q);
    
  return 0;
}



Measured memory_bytes: 3136
#include<bits/stdc++.h>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define endl  "\n"
#define ll long long
#define int long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cin.exceptions(cin.failbit);cout.tie(NULL);
using namespace std;
bool isPrime(int n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i += 6)
    {
        if ((n % i == 0) || (n % (i + 2) == 0))
            return false;
    }
    return true;
}

int32_t main()
{
	int a;
	cin >> a;
	cout << a+a*a + a*a*a;
}



Measured memory_bytes: 3584
package main

import (
	"fmt"
)

func main() {
	var c500, c100, c50, x, res int
	fmt.Scan(&c500)
	fmt.Scan(&c100)
	fmt.Scan(&c50)
	fmt.Scan(&x)
	for i := 0; i <= c500; i++ {
		if 500*i == x {
			res++
			continue
		}
		for j := 0; j <= c100; j++ {
			if 500*i+100*j == x {
				res++
				break
			}
			for k := 0; k <= c50; k++ {
				if 500*i+100*j+50*k == x {
					res++
					break
				}
			}

		}

	}

	fmt.Println(res)
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct Path {
	int to, v;
	Path (int To = 0, int V = 0)
	{
		to = To;
		v = V;
	}
};
void node (int l, int r, int d);
vector <Path> ph[100000 + 9];//记录从 i 点出发的边 
bool vis[100000 + 9], inQ[100000 + 9];
int dis[100000 + 9];
bool dfs(int s);
int main()
{
	int n, m;
	
	cin >> n >> m;
	for (int i = 1; i <= m; i++ )
	{
		int l, r, d;
		cin >> l >> r >> d;
		node (r, l, d);
		node (l, r, -d);
	}
	for (int i = 1; i <= n; i++)
		if (dfs(i) == false)
		{
			cout << "No" << endl;
			return 0;
		}
	cout << "Yes" << endl;
	
}
bool dfs(int s)
{
//	if (vis[s] = true) return true;
	inQ[s] = true;
//	vis[s] = true;
	for (int i = 0; i < ph[s].size(); i++)
	{
		Path e = ph[s][i];
		if (dis[e.to] < dis[s] + e.v)
		{
			if (inQ[e.to])
				return false;
			dis[e.to] = dis[s] + e.v;
			if (dfs(e.to) == false)
				return false;
		}
	}
	inQ[s] = false;
	return true;
}
void node (int x1, int x2, int v)
{
	ph[x1].push_back(Path(x2, v));
}

Measured memory_bytes: 11136
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <list>
    
using namespace std;    
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
    
vector<bool> makePrimeTable(ll x){
    vector<bool> primeTable(x + 1);
    for(ll i = 0; i <= x; i++){
        primeTable[i] = true;
    }

    for(ll i = 2; i * i <= x; i++){
        if(primeTable[i]){
            for(ll j = i + i; j <= x; j += i){
                primeTable[j] = false;
            }
        }
    }
    return primeTable;
}

int main(){

    auto primeTable = makePrimeTable(55555);

    int N;
    cin >> N;

    vector<int> ans;
    for(int i = 0; i < primeTable.size(); i++){
        if(primeTable[i]){
            if( (i + 1) % 5 == 0 ){
                ans.push_back(i);
            } 
        }
        if(ans.size() == N) break;
    }        

    for(int i = 0; i < N; i++) cout << ans[i] << endl;
}

Measured memory_bytes: 256
N = gets.to_i
A = gets.split.map(&:to_i)
T = gets.split.map(&:to_i)

puts (0...N).reduce(1) { |a,i|
  amin = (i == 0 || A[i] > A[i-1]) ? A[i] : 1
  tmin = (i == N-1 || T[i] > T[i+1]) ? T[i] : 1
  a = (a * [[A[i],T[i]].min - [amin, tmin].max + 1, 0].max) % 1000000007
}


Measured memory_bytes: 19476
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<numeric>
#include<vector>
#include<iomanip>
#include<cmath>
using namespace std;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
#define rep(i, n) for (i32 i = 0; i < (i32)(n); i++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using P = pair<i64,i64>;

int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 n,k;
cin >> n >> k;
vector<i64> bottom(n);
rep(i,n){
    i64 tmp = i + 1;
    i64 cnt = 0;
    while(tmp < k){
        tmp *= 2;
        cnt++;
    }
    bottom[i] = pow(2,cnt);
}
/*rep(i,n){
    cout << bottom[i] << " \n"[i == n - 1];
}*/
vector<i64> top(n);
i64 f = bottom[0];
rep(i,n){
    f = lcm(f,bottom[i]);
}
i64 sum = 0;
rep(i,n){
    top[i] = f / bottom[i];
    sum += top[i];
}
/*rep(i,n){
    cout << top[i] << " \n"[i == n - 1];
}*/
f *= n;
//cout << sum <<" " <<  f << endl;
cout << setprecision(10) << ((long double)(sum) / (long double)(f)) << endl;
}

Measured memory_bytes: 5260
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define INF 1e9

static const int seed=702;
static const int D=365;
static const int ntype=26;
static int ans[D+1];
static int max_score=-INF;
static int t=120000;
class Contest{
public:
    Contest(){
        last=0;
    }
    int s[D+1];
    int c;
    int last;
};

static Contest contest[ntype+1];

void Input(){
    int d;
    cin>>d;
    for(int i=1;i<=ntype;++i){
        int t;
        cin>>t;
        contest[i].c=t;
    }
    for(int day=1;day<=D;++day){
        for(int type=1;type<=ntype;++type){
            int t;
            cin>>t;
            contest[type].s[day]=t;
        }
    }
}

int evaluate(){
    int sum=0;
    vector<int> l(ntype+1,0);
    for(int day=1;day<=D;++day){
        int type=ans[day];
        sum+=contest[type].s[day];
        l[type]=day;
        for(int t=1;t<=ntype;++t){
            sum-=contest[t].c*(day-l[t]);
        }
    }
    return sum;   
}

void Output(){
    for(int d=1;d<=D;++d) cout<<ans[d]<<endl;
}

void Init(){
    for(int d=1;d<=D;++d) ans[d]=rand()%ntype+1;
}

void Greedy(){
    vector<int> l(ntype+1,0);
    int score=0;
    for(int d=1;d<=D;++d){
        for(int i=1;i<=ntype;++i) score-=contest[i].c*(d-l[i]);
        int temp=score;
        int t=-1;
        for(int i=1;i<=ntype;++i){
            int k=contest[i].s[d]+contest[i].c*(d-l[i])+score;
            if(k>temp){
                temp=k;
                t=i;
            }
        }
        ans[d]=t;
        l[t]=d;
    }
}

void change(){
    int p=rand()%D+1;
    int temp=ans[p];
    ans[p]=rand()%ntype+1;
    int temp_score=evaluate();
    if(max_score<temp_score) max_score=temp_score;
    else ans[p]=temp;
}

void swap(){
    int p1=rand()%D+1;
    int p2=rand()%D+1;
    while(p1==p2) p2=rand()%D+1;
    int temp=ans[p1];
    ans[p1]=ans[p2];
    ans[p2]=temp;
    int temp_score=evaluate();
    if(max_score<temp_score) max_score=temp_score;
    else{
        ans[p2]=ans[p1];
        ans[p1]=temp;
    }
}

void solve(int times){
    int n=times/3;
    max_score=evaluate();
    for(int i=0;i<n;++i){
        change();
        swap();
        change();
    }
}

int main(){
    srand(seed);
    Input();
    Greedy();
    solve(t);
    Output();
}


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

cnt = s.count("R") * s.count("G") * s.count("B")

for i in range(n - 1):
    tmp = s[i]
    for j in range(i + 1, (n + i + 1) // 2):
        if s[2 * j - i] != s[j] and s[j] != tmp and s[2 * j - i] != tmp:
            cnt -= 1
print(cnt)

Measured memory_bytes: 9200
#include<bits/stdc++.h>
using namespace std;
long long m=1e9+7;

long long power(long long x, long long y, long long p)
{
    long long res = 1;
    x = x % p;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1) res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}

int main()
{
    long long n,k;
    cin>>n>>k;
    long long count[k+1]={0};
    for(long long i=1; i<=k; i++)
    {
        long long x=k/i;
        count[i]=power(x,n,m);
    }
    long long ans=0;
    for(long long i=k; i>=1; i--)
    {
        if(count[i]==0) continue;
        for(long long j=2; i*j<=k; j++)
            count[i]=(count[i]-count[i*j]+m)%m;
        ans=(ans+(count[i]*i)%m)%m;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 4364
#include<stdio.h>
#define M 1000000

void insertionSort(int [], int, int);
void shellSort(int [],int);

int cnt = 0;

main(){
  int i,j,n,a[M];

    scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  shellSort(a, n);
  printf("%d\n",cnt);
  for(i=0;i<n;i++){
    printf("%d\n",a[i]);
  }
  return 0;
}

void insertionSort(int a[], int n, int g){
  
  int i,j,v;
  for(i=g;i<n;i++){
    v=a[i];
    j=i-g;
    while(j>=0 && a[j]>v){
      a[j+g]=a[j];
      j=j-g;
      cnt++;
    }
    a[j+g]=v;
  }
}


void shellSort(int a[],int n){
  
  int i,m = 0;
  
  int G[n];

  G[0]=0;
  for(i=0;i<n;i++){
    G[i+1]=3*G[i]+1;
    m++;
    if(G[i+1]>M){
      break;
    }
  }
  while(G[m] > n){
    m--;
  }
  printf("%d\n",m);
  for(i=m;i>1;i--){
    printf("%d ",G[i]);
  }
  printf("%d\n", G[1]);
  for(i=m;i>=0;i--){
    insertionSort(a, n, G[i]);
  }
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int ans[334][334];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // cout<<setprecision(10)<<fixed;
  int h, w, k;
  char s[334][334];
  cin>>h>>w>>k;
  int cnt=0;
  REP(i, h)REP(j, w){
    cin>>s[i][j];
    if(s[i][j]=='#'){
      ans[i][j]=++cnt;
    }
  }
  REP(i, h)REP(j, w){
    if(s[i][j]=='#'){
      FORR(y, 0, j){
        if(ans[i][y]){
          break;
        }
        ans[i][y]=ans[i][j];
      }
      FOR(y, j+1, w){
        if(ans[i][y]){
          break;
        }
        ans[i][y]=ans[i][j];
      }
    }
  }
  REP(i, h)REP(j, w){
    if(ans[i][j]){
      continue;
    }
    FOR(x, i+1, h){
      if(ans[x][j]){
        ans[i][j]=ans[x][j];
        break;
      }
    }
    if(ans[i][j]){
      continue;
    }
    FORR(x, 0, i){
      if(ans[x][j]){
        ans[i][j]=ans[x][j];
        break;
      }
    }
  }
  REP(i, h){
    REP(j, w){
      cout<<ans[i][j]<<" \n"[j==w-1];
    }
  }
  return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
// typedef long  l;
typedef pair<int,int> P;
const ll INF=100000000000000001;
const double PI=3.141592653589;

int main(){
  int n,k; cin>>n>>k;
  vector<int> h(n);
  rep(i,n) cin>>h[i];

  sort(h.begin(),h.end());
  int l=0;
  int ans=1000000009;
  for(int r=k-1;r<n;r++){
    ans=min(ans,h[r]-h[l]);
    l++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define MOD 100000000000000000
#define UB upper_bound
#define LB lower_bound
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
using namespace std;
/////number of edges in a graph equal (v[i].size() ka summation of all the vertices)//
int main()
{
    fast;
    //#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //#endif	
    ll int x,y,z;
    cin>>x>>y>>z;
    swap(x,y);
    swap(x,z);
    cout<<x<<" "<<y<<" "<<z<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int n, x, i, l, c=0;
    scanf("%d %d", &n, &x);
    int arr[n+1];
    arr[0] = 0;
    for(i=1;i<=n;i++){
        scanf("%d", &l);
        arr[i] = arr[i-1] + l;
    }
    for(i=0;i<=n;i++){
        if(arr[i]<=x){
            c++;
        }
    }
    printf("%d\n", c);

    return 0;
}


Measured memory_bytes: 128
function Main(input) {
  const inputs = input.split('\n');
  const n = Number(inputs[0]);
  const strs = inputs[1]
    .split('');
  
  console.log(strs.map(function(s) {
    var c = s.charCodeAt() + n;
    if (c > 90) {
      c -= 26;
    }
    return String.fromCharCode(c)
  }).join(''));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7500
s = input()
q = int(input())

rev = 0
front = ""
back = ""
all_rev = 0

for i in range(q):
    t = input().split()

    # T_1 = 1の時
    if len(t) == 1:
        rev += 1
        all_rev += 1

    # T_1 = 2の時
    else:
        if rev%2 == 1:
            if t[1] == '1':
                back = back + t[2]
            else:
                front = t[2] + front
        else:
            if t[1] == '1':
                front = t[2] + front
            else:
                back = back + t[2]

# 反転するとき
if all_rev%2 == 1:
    s = s[::-1]
    front,back = back[::-1],front[::-1]

print(front + s + back)
    


Measured memory_bytes: 4512
Printf.printf "%d\n" @@
Scanf.scanf "%d %d\n" @@ fun n l ->
    let flavors = Array.init n (fun i -> i + l) in
    let total = Array.fold_left ( + ) 0 flavors in
    Array.fold_left (fun x eat -> if abs x < abs eat then x else eat) 300 flavors
    |> ( - ) total;;
    


Measured memory_bytes: 3848
import core.bitop, std.bitmanip;
import core.checkedint;
import std.algorithm, std.functional, std.meta;
import std.array, std.container;
import std.bigint;
import std.conv;
import std.math, std.numeric;
import std.range, std.range.interfaces;
import std.stdio, std.string;
import std.ascii, std.typecons;

void main()
{
    int k;
    readf("%s", &k);
    readln;
    
    string s = readln.chomp;

    class mod {
        static:
        const int MD = 10 ^^ 9 + 7;
    
        int mul(int a, int b) {
            return a.to!long * b % MD;
        }
        
        int add (int a, int b) {
            return (a.to!long + b) % MD;
        }
        
        int fstpw(int a, int p) {
            if (p == 0) { return 1; }
            if (p == 1) { return a; }

            int odd = p % 2 == 1 ? a : 1;

            int sub = fstpw(a, p / 2);

            return sub.to!long * sub % MD * odd % MD;
        }
        
        int invf(int x) {
            return fstpw(x, MD - 2);
        }
    }
  
    auto slen = s.length.to!int;
    auto totlen = slen + k;
    
    auto fact = new int[] (totlen + 1);
    fact[0] = 1;
    foreach (i; 1 .. totlen + 1) { fact[i] = mod.mul(fact[i-1], i); }
    
    auto inv = new int[] (totlen + 1);
    inv[totlen] = mod.invf(fact[totlen]);
    foreach_reverse (i; 0 .. totlen) { inv[i] = mod.mul(inv[i+1], i+1); }
    
    auto nCk = new int[] (totlen + 1);
    nCk[slen-1] = 1;
    foreach (i; slen .. totlen + 1) {
        nCk[i] = mod.mul(fact[i], mod.mul(inv[i - (slen-1)], inv[slen-1]));
    }
    
    auto invAlpha = mod.invf('z' - 'a' + 1);
    auto inBetween = 1;
    auto rightSide = mod.fstpw('z' - 'a' + 1, k);
    
    auto ans = 0;
    foreach (clen; slen .. totlen + 1) {
        auto cur = mod.mul(nCk[clen-1], mod.mul(inBetween, rightSide));
        ans = mod.add(ans, cur);
        
        inBetween = mod.mul(inBetween, 'z' - 'a' + 1 - 1);
        rightSide = mod.mul(rightSide, invAlpha);
    }
    
    ans.writeln;
}

Measured memory_bytes: 27300
#include<iostream>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int main(int argc, char const *argv[])
{
    int a,b;
    cin>>a>>b;
    if(b%a==0){
        cout<<a+b;
    }else{
        cout<<b-a;
    }
    /* code */
    return 0;
}


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

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

  int x;
  cin >> x;

  int d = 360 / __gcd(360, x) * x;
  cout << d / x << '\n';

  return (0);
}


Measured memory_bytes: 3616
n = int(input())
a = [0 for _ in range(4)]
b = ['AC', 'WA', 'TLE', 'RE']
for _ in range(n):
    s = input()
    a[b.index(s)] += 1
print("AC x " + str(a[0]))
print("WA x " + str(a[1]))
print("TLE x " + str(a[2]))
print("RE x " + str(a[3]))

Measured memory_bytes: 9208
K = int(input())
# A,B = map(int,input().split())
# S = input()
# X1_list = [int(input()) for i in range(N)]
# X2_list = [list(map(int,input().split())) for i in range(N)]
base = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
result = [1, 2, 3, 4, 5, 6, 7, 8, 9]


def make_lun_lun(tempresult, n):
    stemp = []
    itemp = []
    if n == 0:
        return
    for r in tempresult:
        sa = r[len(r) - 1]
        ia = int(r[len(r) - 1])
        # print(r[len(r) - 1])
        if ia - 1 > -1:
            stemp.append(r + str(ia - 1))
            itemp.append(int(r + str(ia - 1)))
        if ia + 1 < 10:
            stemp.append(r + str(ia + 1))
            itemp.append(int(r + str(ia + 1)))
        stemp.append(r + sa)
        itemp.append(int(r + sa))
    result.extend(itemp)
    make_lun_lun(stemp, n - 1)


make_lun_lun(base, 9)
# print(result)
print(sorted(result)[K - 1])
# print(result)


Measured memory_bytes: 27076
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long int
int main()
{

    string n;

    cin>>n;

    ll sum = 0;

    for(auto i:n) {
        sum+=i-'0';
    }

    if(sum%9==0) cout<<"Yes";
    else cout<<"No";
    
}

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

int bs()
{
    int n;
    n = 10;
    int lo=0,hi=n;
    int key;
    key = 100;
    int arr[n] = {9,24,56,99,102,244,654,765,999,1002};
    while(lo < hi)
    {
        int md = (hi+lo)/2;//lo+(hi-lo)/2; lo+(hi-lo+1)/2;
        if(arr[md] > key)
        {
            hi = md-1;
        }
        else if(arr[md] < key)
        {
            lo = md+1;
        }
        else
        {
            return cout<<md<<endl,0;
            //hi = md;
            //lo = md;
        }
    }
}
int main()
{
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if((i+1)%2 && s[i] == 'L' || ((i+1)%2==0 && s[i] == 'R'))return puts("No"),0;
    }
    cout<<"Yes";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define inf 10000000000000007
#define eps 1e-8
#define PI 3.14159265359
#define sp printf(" ")
#define vi vector<int>
#define vl vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pcc pair<char, char>
#define mp make_pair
#define FF first
#define SS second
#define pb(x) push_back(x)
#define sd(x) scanf("%d", &(x))
#define pd(x) printf("%d", (x))
#define pdn(x) printf("%d\n", (x))
#define sld(x) scanf("%ld", &(x))
#define pld(x) printf("%ld", (x))
#define pldn(x) printf("%ld\n", (x))
#define slf(x) scanf("%lf", &(x))
#define plf(x) printf("%.9lf", (x))
#define plfn(x) printf("%.4lf\n", (x))
#define sch(x) scanf("%c", &(x))
#define pch(x) printf("%c", (x))
#define pchn(x) printf("%c\n", (x))
#define gtl(x) getline(cin, (x))
#define flsh fflush(stdout)
#define ios ios::sync_with_stdio(false); cin.tie(0) ; cout.tie(0)
#define endl '\n'
using namespace std;
int p[100004],vis[100004],vis1[100003];
int cnt=0;
vector<int>a[100004],v;
void dfs(int i)
{
    vis[i]=cnt;
    vis1[p[i]]=cnt;
    v.pb(i);
    for(int j=0;j<a[i].size();j++)
    {
        if(vis[a[i][j]]==0)dfs(a[i][j]);
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>p[i];
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x].pb(y);
        a[y].pb(x);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            v.clear();
            cnt++;
            dfs(i);
            for(int i=0;i<v.size();i++)
            {
                if(vis[v[i]]==vis1[v[i]])ans++;
            }
        }
    }
    cout<<ans<<endl;

    
   
}

Measured memory_bytes: 9596
#include<stdio.h>
int main(void) {
	int a, b, c;
	int sum = 0;
 
	scanf("%d %d %d", &a, &b, &c);
	if (a >= b && a >= c) {
		sum = b + c;
	}
	else if (b >= a && b >= c){
		sum = a + c;
	}
	else {
		sum = a + b; 
	}

 
	printf("%d\n", sum);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <unordered_map>
#include <limits>
#include <set>
//std::numeric_limits<int>::max(), min()


std::unordered_map<int,int> dp;
int s[7], n[7];

int sol ( int i ) {
  if ( dp.count(i) != 0 ) return dp[i];

  int cost_min = std::numeric_limits<int>::max();
  for(int j=0; j<=6 && (i-s[j])>=0; j++) cost_min = std::min(sol(i-s[j])+1, cost_min);
  for(int j=1; j<=6 && (i-n[j])>=0; j++) cost_min = std::min(sol(i-n[j])+1, cost_min);

  return dp[i] = cost_min;
}

int main (void) {

  int N;
  std::cin >> N;

  for(int i=0; i<=6; i++){
    s[i] = std::pow(6, i);
    n[i] = std::pow(9, i);
  }

  dp[0] = 0;
  dp[1] = 1;
  std::cout << sol(N) << std::endl;

  return 0;
}

Measured memory_bytes: 8996
// In the name of God

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, d;
	cin >> n >> m >> d;


	long long pairs = d ? 2 * (n-d) : n;

	double p = 1.0 * pairs / (1ll*n*n);

	cout << fixed << setprecision(10) << (m-1) * p;


	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

int main(){
	string s;
	getline(cin, s);
	char last;
	std::string::iterator it; 
	it = s.end()-1;
	last = *it;
	if(last=='s'){
		s.push_back('e');
		s.push_back('s');
	}
	else s.push_back('s');
	cout<<s;
	
	return 0;
}

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

int main()
{
  string s;
  while (cin >> s) {
    vector<int> cnt(26, 0);
    for (unsigned int i = 0; i < s.size(); ++i)
      ++cnt[s[i]-'a'];

    int odd = 0;
    for (unsigned int i = 0; i < cnt.size(); ++i) {
      if (cnt[i] & 1)
	++odd;
    }

    long long int ans = 1LL;
    for (int i = 2; i <= s.size()/2; ++i)
      ans *= i;

    for (unsigned int i = 0; i < cnt.size(); ++i) {
      long long int fact = 1LL;
      for (int j = 2; j <= cnt[i]/2; ++j)
	fact *= j;
      ans /= fact;
    }

    if (odd > 1)
      ans = 0LL;
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <string.h>


int main(){

    char s1[10], s2[10];
    int a=0,b=0,cnt=0,n;
    scanf("%d",&n);
    while(cnt<n){
    scanf("%s %s", s1, s2);
    if ( strcmp(s1, s2) == 0 )
    {a+=1;b+=1;}
    else if ( strcmp(s1, s2) > 0 )
        a+=3;
    else if ( strcmp(s1, s2) < 0 )
        b+=3;
        cnt++;

    }
    
    printf("%d %d\n",a,b);
    return 0;
}



Measured memory_bytes: 2056
#include <bits/stdc++.h>
#define int long long
#define all(c) (c).begin(),(c).end()

using namespace std;

signed main()
{
int n,m,A;
A=0;
cin>>n>>m;
vector<int> a(n,0);
for(int i=0; i<n; i++){
	cin>>a[i];
}
int sum =0;
for(int i=0; i<n; i++){
	sum = sum+a[i];
}
int p = 4*m;
int val = sum/p;
bool b  = sum%p;

if(b){
	val++;
}
for(int i=0; i<n; i++){
	if(a[i]>=val){
		A++;
	}
}

if(A>=m){
	cout<<"Yes";
}
else{
	cout<<"No";
}

}
	


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

void solve() {
    int N, W;
    cin >> N >> W;
    vll dp(W + 1);
    rep(i, N) {
        int w, v;
        cin >> w >> v;
        for (int j = W - w; j >= 0; --j) {
            smax(dp[j + w], dp[j] + v);
        }
    }
    cout << dp.back() << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 1024
while line=gets
	line=line.chomp.split(",").map{|s| s.to_i}
	length=(0..9).map{|i| line[0..i].inject{|sum,j| sum+j}}
	v1=line[10]
	v2=line[11]
	p=length[9]*v1/(v1+v2).to_f
	10.times{|i|
		if p<=length[i] then
			puts i+1
			break
		end
	}
end


Measured memory_bytes: 6864
cands = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def add_v(v):
  global cands
  global K
  v = str(v)
  v0 = int(v[-1])
  if v0 == 0:
    cands += [int(v+'0'), int(v+'1')]
    K -=2
  elif v0 == 9:
    cands += [int(v+'8'), int(v+'9')]
    K -= 2
  else:
    cands += [int(v+str(v0-1)), int(v+str(v0)), int(v+str(v0+1))]
    K -= 3

K = int(input())
idk = K
K -= 9
idx = 0
while K >= 0:
  add_v(cands[idx])
  idx += 1

print(cands[idk-1])

Measured memory_bytes: 7044
#include <iostream>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#define ull unsigned long long;
using namespace std;

int main()
{
	long long N=0,X=0;
	cin >> N >> X;
	long long ans=0,x[N+1];
	x[N]=X;
	for (int i = 0; i < N; i++){
		cin >> x[i];
	}
	sort(x,x+N+1);
	for (int i = 1; i <= N; i++){
		if(i==1) ans=x[i]-x[i-1];
		ans = __gcd(ans,x[i]-x[i-1]);
	}
	cout << ans << endl;
	return 0;
}

//関数


Measured memory_bytes: 1024
#include <stdbool.h>
#include <stdio.h>

int main(void)
{
	int player_1_hp;
    int player_1_atack;
  	int player_2_hp;
    int player_2_atack;
  	bool in_battle = true;

	scanf("%d %d %d %d",
          &player_1_hp, &player_1_atack,
          &player_2_hp, &player_2_atack);
  	
  	while (in_battle)
  	{
    	player_2_hp -= player_1_atack;
        if (player_2_hp <= 0)
        {
          	in_battle = false;
        }
      	else
        {
			player_1_hp -= player_2_atack;;
            if (player_1_hp <= 0)
            {
                in_battle = false;
            }
        }
  	}

  	if (0 < player_1_hp)
  	{
      	puts("Yes");
  	}
  	else
    {
     	puts("No"); 
    }

  	return 0;
}

Measured memory_bytes: 1660
// #pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")

// #include <bits/extc++.h>
// using namespace __gnu_pbds;

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
// template <typename T>
// using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RANDOM() random_device __rd; \
                 mt19937 __gen = mt19937(__rd()); \
                 uniform_int_distribution<int> __dis(1, 1E8); \
                 auto rnd = bind(__dis, __gen)

const int INF = 1E18;
const int mod = 1E9 + 7;
const int maxn = 100 + 5;
const int maxm = 1000 + 5;

vector<pii> adj[maxn];
int vis[maxn], dis[maxn], cnt[maxn][maxn];

void dijkstra(int now) {
    memset(vis, 0x00, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));
    dis[now] = 0;
    
    prior<pii> pq;
    pq.push({0, now});
    
    while (!pq.empty()) {
        now = pq.top().Y; pq.pop();
        if (vis[now]) continue;
        vis[now] = 1;
        
        for (auto x : adj[now]) {
            if (vis[x.X]) continue;
            if (dis[x.X] > dis[now] + x.Y) pq.push({dis[x.X] = dis[now] + x.Y, x.X});
        }
    }
}

int32_t main() {
    fastIO();
    
    int n, m;
    cin >> n >> m;
    
    vector<int> e1(m), e2(m), e3(m); /// from , to , dis ///
    for (int i = 0; i < m; ++i) {
        cin >> e1[i] >> e2[i] >> e3[i];
        if (e1[i] > e2[i]) swap(e1[i], e2[i]);
        adj[e1[i]].eb(e2[i], e3[i]), adj[e2[i]].eb(e1[i], e3[i]);
    }
    
    for (int i = 1; i <= n; ++i) {
        dijkstra(i);
        for (int j = 0; j < m; ++j) {
            if (abs(dis[e1[j]] - dis[e2[j]]) == e3[j]) ++cnt[e1[j]][e2[j]];
        }
    }
    
    int ans = 0;
    for (int i = 0; i < m; ++i) {
        if (!cnt[e1[i]][e2[i]]) ++ans;
    }
    cout << ans << "\n";
    
    return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;

const int MAXN = 500005;

int N;
char s[MAXN];
set <int> dec;
set <int> pos[10];

void load() {
	scanf("%s", s);
}

void change(int x, char ch) {
	pos[s[x] - '0'].erase(x);
	dec.erase(x);
	dec.erase(x - 1);
	s[x] = ch;
	pos[s[x] - '0'].insert(x);
	if (x < N - 1 && s[x] > s[x + 1])
		dec.insert(x);
	if (x && s[x - 1] > s[x])
		dec.insert(x - 1);
}

int solve() {
	N = strlen(s);
	
	for (int i = 0; i < N; i++)
		pos[s[i] - '0'].insert(i);
		
	for (int i = 0; i < N - 1; i++)
		if (s[i] > s[i + 1])
			dec.insert(i);
	
	int sol = 1, last = -1;
	while (!dec.empty()) {
		int curr = *dec.begin();
		int prev = *pos[s[curr] - '0'].begin();
		int it = N - 1;
		for (; it > curr && s[it] == '9'; it--)
			change(it, '0');
		change(it, s[it] + 1);
		for (int i = prev; i > last; i--)
			change(i, '0');
		last = prev;
		sol++;
	}	
	
	return sol;
}

int main() {
	load();
	printf("%d\n", solve());
	return 0;
}

Measured memory_bytes: 36736
#include <stdio.h>
    int main(void){
    int a,b,c,d,e,i;
    scanf("%d %d\n",&a,&b);
    c = b - a;
    d = 0;
    for(int i = 1;i <= c;i++){
    d = d + i;
     }
    e = d - b;
    printf("%d\n",e);
    return 0;
    }

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;
int main()
{
	long int n;
	cin>>n;
	long int arr[n];
	for ( int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	long int min_cost=INT_MAX;
	for( int i=-100;i<=100;i++)
	{
		long int cost=0;
		for( int j=0;j<n;j++)
		{
			cost+=pow(abs(arr[j]-i),2);
		}
		if(cost<min_cost)
			min_cost=cost;
	}
	cout<<min_cost<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i=0;i<n;i++)arr.add(sc.nextInt());
        Collections.sort(arr);
        int pre = 0, ans = 0;
        for(int i=0;i<n;i++) {
            if (arr.get(i) != pre) {
                pre = arr.get(i);
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 23252
mod = 10**9+7
n, x, y, z = map(int,input().split())
xyz = 2**(x+y+z-1) + 2**(y+z-1) + 2**(z-1)
w = 2**(x+y+z-1)
dp = [[0]*w for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(w):
        for k in range(1,11):
            nj = ((j+j+1)<<(k-1))
            if nj&xyz != xyz:
                dp[i+1][nj%w] = (dp[i+1][nj%w]+dp[i][j])%mod

print((pow(10,n,mod)-sum(dp[-1])%mod)%mod)


Measured memory_bytes: 62812
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main(){
  ll h,n;
  cin>>h>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];

  ll sum=0;
  for(int i=0;i<n;i++) sum+=a[i];
  if(sum >= h) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 640
#include <stdio.h>

int main() {

	int n, m;
//	int i;

	int even_num = 0;
	int odd_num = 0;
	int total;

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

	if(n >= 2) {
		even_num = n * (n-1) / 2;
	}
	if(m >= 2) {
		odd_num = m * (m-1) / 2;
	}

	total = even_num + odd_num;

	printf("%d", total);

	return 0;

}


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

int main() {
	// your code goes here
	int h,n;
	cin>>h>>n;
	int arr[n];
	int sum=0;
	for(int i=1;i<=n;i++)
	{
	    cin>>arr[i];
	    sum+=arr[i];
	}
	if(h/sum==0||(h/sum==1&&h%sum==0))
	cout<<"Yes";
	else
	cout<<"No";
}


Measured memory_bytes: 640