akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const int maxn=100100;
set<int> sak1[maxn],sak2[maxn];
set<int>::iterator it,itt;
struct node{
	int s,t;
};
queue<node> q;
int sum[maxn];
int f[maxn];
int fa(int x){
	if(f[x]==x) return x;
	return f[x]=fa(f[x]);
}
int zs,zt;
int stk[maxn],top;
void merge(int s,int t){
//	if(s==t) return ;
	int v;
	sum[t]+=sum[s];
	f[s]=t;

	it=sak1[s].begin();

	while(it!=sak1[s].end()){
		v=*it;
		if(t!=v)
		{
			itt=sak2[t].lower_bound(v);
			if(itt!=sak2[t].end()&&*itt==v)
				q.push((node){t,v});
			stk[++top]=v;

			itt=sak1[v].lower_bound(s);
			sak1[v].erase(itt);
			sak1[v].insert(t);
		}
		it++;
	}
	sak1[s].clear();

	it=sak2[s].begin();
	while(it!=sak2[s].end()){
		v=*it;
		if(fa(t)!=fa(v))
		{
			itt=sak1[t].lower_bound(v);
			if(itt!=sak1[t].end()&&*itt==v)
				q.push((node){t,v});
			sak2[t].insert(v);

			itt=sak2[v].lower_bound(s);
			sak2[v].erase(itt);
			sak2[v].insert(t);
		}
		it++;
	}
	sak2[s].clear();
	while(top){
		sak1[t].insert(stk[top]);
		top--;
	}
	it=sak1[t].lower_bound(s);
	sak1[t].erase(s);
	it=sak2[t].lower_bound(s);
	sak2[t].erase(s);
}
int main(){
//	freopen("E.in","r",stdin);
	int n;
	scanf("%d",&n);
	int s,t;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&s,&t);
		sak1[s].insert(t);
		sak1[t].insert(s);
	}
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&s,&t);
		sak2[s].insert(t);
		sak2[t].insert(s);
		itt=sak1[s].lower_bound(t);
		if(itt!=sak1[s].end()&&*itt==t)
			q.push((node){s,t});
		sum[s]++,sum[t]++;
	}
	for(int i=1;i<=n;i++)
		f[i]=i;
	node st;
	while(!q.empty()){
		st=q.front();
		q.pop();
		zs=st.s,zt=st.t;
		s=fa(st.s),t=fa(st.t);
		if(sum[s]>sum[t])
			merge(t,s);
		else
			merge(s,t);
	}
	for(int i=2;i<=n;i++){
		if(fa(i)!=fa(i-1))
		{
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	return 0;
}


Measured memory_bytes: 29440
#include <bits/stdc++.h>
#define LL long long
#define FOR(i,c) for(__typeof(c.begin()) i = c.begin(); i != c.end(); i++)
#define F first
#define S second
using namespace std;

const LL mod = 1e9 + 7;

template<typename T> T gcd(T a, T b) { return b == 0?a: gcd(b, a % b); }
template<typename T> T LCM(T a, T b) { return a*(b/gcd(a, b)); }
template<typename T> T expo(T base, T e, T mod) { T res = 1;
  while(e > 0) { if(e&1) res = res * base % mod; base = base * base % mod; e >>= 1; }
  return res;
}
template<typename T, typename S> T expo(T b, S e){if(e <= 1)return e == 0?1: b;\
	return (e&1) == 0?expo((b*b), e>>1): (b*expo((b*b), e>>1));}
template<typename T, typename S> T modinv(T a, S mod) { return expo(a, mod-2, mod); }
template<class T, class S> std::ostream& operator<<(std::ostream &os, const std::pair<T, S> &t) {
	os<<"("<<t.first<<", "<<t.second<<")";
	return os;
}
template<class T> std::ostream& operator<<(std::ostream &os, const std::vector<T> &t) {
	os<<"["; FOR(it,t) { if(it != t.begin()) os<<", "; os<<*it; } os<<"]";
	return os;
}

const int MAXN = 1e5 + 3;
int n;
string s;
bool is_sheep[MAXN];

int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  cin >> s;
  for(int i = 0; i < 2; i++) {
    for(int j = 0; j < 2; j++) {
      // Assume 0 is i, 1 is j
      memset(is_sheep, false, sizeof is_sheep);
      is_sheep[0] = i;
      is_sheep[1] = j;
      for(int x = 2; x < n; x++) {
        if(is_sheep[x-1]) {
          if(s[x-1] == 'o') {
            is_sheep[x] = is_sheep[x-2];
          } else {
            is_sheep[x] = !is_sheep[x-2];
          }
        } else {
          if(s[x-1] == 'o') {
            is_sheep[x] = !is_sheep[x-2];
          } else {
            is_sheep[x] = is_sheep[x-2];
          }
        }
      }
      bool ok = false;
      if(is_sheep[0]) {
        if(s[0] == 'o') {
          ok = is_sheep[n-1] == is_sheep[1];
        } else {
          ok = is_sheep[n-1] != is_sheep[1];
        }
      } else {
        if(s[0] == 'o') {
          ok = is_sheep[n-1] != is_sheep[1];
        } else {
          ok = is_sheep[n-1] == is_sheep[1];
        }
      }
      if(ok) {
        if(is_sheep[n-1]) {
          if(s[n-1] == 'o') {
            ok = is_sheep[n-2] == is_sheep[0];
          } else {
            ok = is_sheep[n-2] != is_sheep[0];
          }
        } else {
          if(s[n-1] == 'o') {
            ok = is_sheep[n-2] != is_sheep[0];
          } else {
            ok = is_sheep[n-2] == is_sheep[0];
          }
        }
      }
      if(ok) {
        for(int i = 0; i < n; i++) {
          cout << (is_sheep[i] ? 'S' : 'W');
        }
        cout << endl;
        return 0;
      }
    }
  }
  cout << -1 << '\n';
  return 0;
}


Measured memory_bytes: 720
//2018.9.25 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
    res s=0;
    bool w=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline void _swap(res &x,res &y){
    x^=y^=x^=y;
}
inline int _abs(const res &x){
    return x>0?x:-x;
}
inline int _max(const res &x,const res &y){
    return x>y?x:y;
}
inline int _min(const res &x,const res &y){
    return x<y?x:y;
}
const int N=1e5+10;
namespace MAIN{
    int n,m;
    int q[N];
    bool p[N];
    int sum;
    inline void MAIN(){
        n=read(),m=read();
        p[1]=1;
        for(res i=1;i<=m;i++){
            res x=read(),y=read();
            if(p[x]){
                if(!q[x])p[x]=0;
                p[y]=1;
            }
            q[x]--,q[y]++;
        }
        for(res i=1;i<=n;i++)if(p[i])sum++;
        printf("%d\n",sum);
    }
}
int main(){
    MAIN::MAIN();
    return 0;
}

Measured memory_bytes: 768
N=int(input())

a=input().split(" ")
b=input().split(" ")
A=[]
B=[]
for i in a:
    A.append(int(i))
for i in b:
    B.append(int(i))
count=0
roof=0
for i in range(len(A)-1):
    enemy=A[i]
    if(roof>0):
        if(enemy>roof):
            count+=roof
            enemy-=roof
        else:
            count+=enemy
            enemy=0
            roof=0
    if(enemy<B[i]):
        count+=enemy
        roof=B[i]-enemy
    else:
        count+=B[i]
        roof=0
enemy=A[-1]
if(roof>0):
    if(enemy>roof):
        count+=roof
        enemy-=roof
    else:
        count+=enemy

print(count)

Measured memory_bytes: 81952
#define _USE_MATH_DEFINES
#include <math.h>
#include <time.h>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <iomanip>
#include <iterator>
#include <algorithm>
#include <typeinfo>

using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define reprrev(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define reprev(i, n) reprrev(i, 0, n)

#define PI M_PI
#define INF 1000000000
#define MOD 1000000007;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<bool>> vvb;
typedef vector<vector<string>> vvs;

constexpr int dir[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };



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

	repr(i, 1, S.length())
	{
		int l = S.length() - i;
		if (l % 2 == 1) continue;

		string s1, s2;
		s1 = S.substr(0, l / 2);
		s2 = S.substr(l / 2, l / 2);

		if (s1 == s2)
		{
			cout << l << endl;
			break;
		}
	}

	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int N;
vector<int>to[100005];

int main() {
	int N, M;
	cin >> N >> M;
	for (int n = 0; n < M; ++n) {
		int a, b;
		cin >> a >> b;
		to[a].push_back(b);
		to[b].push_back(a);
	}
	int ans = 0;
	vector<int> v;
	for (int n = 0; n < N; ++n) {
		v.push_back(n + 1);
	}
	do {
		bool b = true;
		for (int i = 0;i<v.size()-1;++i) {
			bool b2 = false;
			for (int e : to[v[i]]) {
				if (e == v[i+1]) {
					b2 = true;
					break;
				}
			}
			if (!b2) {
				b = false;
			}
		}
		if (b) {
			ans++;
		}
	} while (next_permutation(v.begin()+1, v.end()));

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

Measured memory_bytes: 5948
#include <iostream>
#include <stack>
#include <queue>

int main()
{
    std::string str;
    std::stack <char> stk, stk2;

    std::cin >> str;

    int strLen = str.length();

    for(int i = 0; i < strLen; i++)
    {
        if(str[i] != 'B')
        {
            stk.push(str[i]);
        }
        else if(!stk.empty())
        {
            stk.pop();
        }
    }

    while(!stk.empty())
    {
        stk2.push(stk.top());
        stk.pop();
    }

    while(!stk2.empty())
    {
        std::cout << stk2.top();
        stk2.pop();
    }

    std::cout << std::endl;

    return 0;
}


Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! invec {
    ( $t:ty ) => {{
        let mut s = String::new();
        match std::io::stdin().read_line(&mut s) {
            Ok(0) => Vec::<$t>::new(),
            Ok(n) => s.trim().split_whitespace().map(|s| s.parse::<$t>().unwrap()).collect::<Vec<$t>>(),
            Err(_) => Vec::<$t>::new(),
        }
    }}
}

#[allow(unused_macros)]
macro_rules! input {
    ( $($t:ty),* ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s);
        let mut splits = s.trim().split_whitespace();
        ($(
            {
                 splits.next().unwrap().parse::<$t>().unwrap()
            },
        )*)
    }}
}

struct Store {
    cost: u64,
    stock: u64
}

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    let (n, m) = input!(usize, u64);
    let mut stores = Vec::<Store>::with_capacity(n);

    for i in 0..n {
        let (cost, stock) = input!(u64, u64);
        stores.push(Store { cost: cost, stock: stock } );
    }

    stores.sort_by(|a, b| a.cost.cmp(&b.cost));
    
    let mut remaining = m;
    let mut ans = 0;
    for store in stores {
        if store.stock <= remaining {
            remaining -= store.stock;
            ans += store.cost * store.stock;
        } else {
            ans += store.cost * remaining;
            remaining = 0;
        }
    }

    println!("{}", ans);
}

fn main() {
    solve();
}


Measured memory_bytes: 6396
import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
x,y=map(int,stdin.readline().split())
poss=True
if(y%2==1):
    poss=False
elif(y<2*x):
    poss=False
elif(y>4*x):
    poss=False
if(poss):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9188
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <map>

typedef long long ll;
#define rep(i, a, n) for(ll i = a; i<n; i++)
#define ALL(a) begin(a), end(a)
using namespace std;
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;
}
vector<int> vec;
int vector_finder(std::vector<ll> vec, ll number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}
int main() {
    string s;
    ll N;
    //vector<vector<int>> data(3, vector<int>(4));

    map<ll, ll> mp;
    cin >> N;
    rep(i, 0, N) {
        ll a;
        cin >> a;
        mp[a] += 1;
    }
    ll res = 0;
  for (auto x:mp) {
      if (x.first > x.second) {
          res += x.second;
      } else if (x.first < x.second) {
          res += x.second -x.first;
      }
  }
    cout << res << endl;
    return 0;
}

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

#define ll long long
#define ld long double
#define tc(t) int t;cin >> t; while(t--)
#define pb push_back
#define fi first
#define se second
#define debug1(x) cerr << #x << " = " << x << '\n';
#define debug2(x, y) cerr << #x << " = " << x << "   " << #y << " = " << y << "\n";
#define _ ios_base::sync_with_stdio(0);cin.tie(NULL);

bool check(string s) {
    bool ok = true;
    for(int i = 0, j = int(s.size())-1; i < j; i++, j--) {
        if(s[i] != s[j]) ok = false;
    }
    return ok;
}

void solve() {
    string s;
    cin >> s;
    int n = int(s.size());
    string t = "", x = "";
    for(int i = 0; i<(n-1)/2; i++) t.pb(s[i]);
    for(int i = (n+3)/2-1; i<n; i++) x.pb(s[i]);
    if(check(s) == true && check(t) == true && check(x) == true) {
        cout << "Yes";
    }
    else
        cout << "No";
}

int main() {_
    int t = 1;
    //cin >> t;
    // Please remember to uncomment for taking test cases
    for(int i = 1; i<=t; i++) {
        solve();
    }
    return 0;
}


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


int main()
{ 
  int n,k;
  cin >> n >> k ;
  int a[1010];
  int c = 0;

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

    cin >> a[i];
  }

  sort(a,a+n);

  for(int i=0;i<k;i++){

    c = c + a[i];

  }

  cout << c << endl;
   
}

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

using namespace std;

int main() {
    string str;
    cin>>str;
    int str_size = str.length();
    int index_last = str_size-1;
    if(str[index_last] == 's')
        cout<<str<<"es"<<endl;
    else
        cout<<str<<"s"<<endl;
    return 0;
}

Measured memory_bytes: 3580
import sys
sys.setrecursionlimit(100000)

H,W=list(map(int,input().split())) # R行 C列 の迷路を受け取る

canv=[]
for i in range(H):
    canv.append([])
    line_input=input() # 迷路を1行取得
    for j in range(W):
        canv[i].append(line_input[j:j+1]) # slice による部分文字列取得

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def dfs(x,y):
    for i in range(4):
        canv[x][y]="."
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx and nx<H and 0<=ny and ny<W:
            if canv[nx][ny]=="#":
                dfs(nx,ny)

for i in range(H):
    for j in range(W):
        for k in range(4):
            nx1 = i + dx[k]
            ny1 = j + dy[k]
            if 0<=nx1 and nx1<H and 0<=ny1 and ny1<W:
                if canv[i][j]=="#" and canv[nx1][ny1]=="#":
                    dfs(i,j)
flg = True
for i in range(H):
    for j in range(W):
        if canv[i][j]=="#":
            flg = False
if flg: print("Yes")
else: print("No")


Measured memory_bytes: 4852
x,n = map(int, input().split())
p=list(map(int, input().split()))


absp= list()
for i in p:
    absp.append(i-x)


absp = sorted(absp, key=abs)


uper, lower = 0, 0
while True:
    if not lower in absp:
        print(x+lower)
        exit()

    elif not uper in absp:
        print(x+uper)
        exit()

    uper += 1
    lower += -1


Measured memory_bytes: 9064
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef long long ll;
typedef double dd;
#define pb push_back
#define mp make_pair
#define endl "\n"
ll const M = 1000000007;
dd const pi = acos(-1);
ll const inf = 2e18;
ll const N = 200001;
int main()
{
    fast;
    ll i,j,t,a,b;
    cin >> a >> b;
    if(b & 1)
    	cout<<"No"<<endl;
    else
    {
    	if(b <= 4*a && b >= 2*a)
    		cout<<"Yes"<<endl;
    	else
    		cout<<"No"<<endl;
    }
    return 0;
}    

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

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;

    for (int i = n; i <= n * 2; i++) {
        if (s.substr(i - n) == t.substr(0, n * 2 - i)) {
            cout << i << '\n';
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#define rg register
using namespace std;
typedef long long ll;
template <typename Tp> inline int getmin(Tp &x,Tp y){return y<x?x=y,1:0;}
template <typename Tp> inline int getmax(Tp &x,Tp y){return y>x?x=y,1:0;}
template <typename Tp> inline void read(Tp &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-') f=1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	if(f) x=-x;
}
int x1,y1,x2,y2,a,b;
int main()
{
	read(x1);read(y1);read(x2);read(y2);
	a=x2-x1;b=y2-y1;
	printf("%d %d %d %d\n",x2-b,y2+a,x2-a-b,y2+a-b);
	return 0;
}

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

int main () {

  int n , b , f , r , v;

  int T[4][3][10] = {0};

  cin >> n ;

  for(int i = n; i > 0 ; i--) {

    cin >> b >> f >> r >> v ;

    T[b - 1][f - 1][r - 1] += v;

  }

  for(int i = 0; i < 4; i++) {

    for(int j = 0; j < 3; j++) {

      for(int k = 0; k < 10; k++) {

	cout << " " << T[i][j][k];

      }

      cout << "\n";

    }

    if(i != 3) {

      cout << "####################" << "\n";

    } else {

      continue;

    }

  }

  return 0;

}

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

#define pb            push_back
#define mp            make_pair
#define all(x)        x.begin(),x.end()
#define debug(X)      { cerr<<'\n'<<(#X)<<" = "<<(X)<<'\n'; }
//#define cerr if(0)cerr

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;


int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,a;
    vector<int> v(100100,0);
    cin>>n;

    for (int i=1; i<=n; ++i) {
        cin>>a;
        v[a] = i;
    }

    int i=1;
    while (v[i]) {
        cout << v[i] << ' ';
        ++i;
    }
    cout<<'\n';
    
    

}



Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
using P = pair<int,int>;
int main()
{
    while(1){
        int x;
        cin >> x;
        if(x == 0)break;
        x = 1000 - x;
        
        int ans = 0;
        ans += x/500;
        x %= 500;
        ans += x/100;
        x %= 100;
        ans += x/50;
        x %= 50;
        ans += x/10;
        x %= 10;
        ans += x/5;
        x %= 5;
        ans += x;
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 2984
#include <iostream>

int main(int argc, const char * argv[]) {
    int A, B;
    std::cin >> A >> B;
    int sum, subtract, mult;
    sum = A+B;
    subtract = A-B;
    mult = A*B;
    
    int tempm, m;
    tempm = std::max(sum, subtract);
    m = std::max(tempm, mult);
    std::cout << m << std::endl;

    return 0;
}

Measured memory_bytes: 256
from operator import itemgetter
N,M = map(int,input().split(' '))
tuple_drink = []
#各店舗の情報を格納
for i in range(N):
  tuple_drink.append(tuple(map(int,input().split(' '))))
tuple_drink.sort(key=itemgetter(0))
#購入したドリンクの本数
num_drink = 0
#合計金額
sum = 0
for i in range(N):
  if tuple_drink[i][1] + num_drink <= M:
      sum += tuple_drink[i][0]*tuple_drink[i][1]
      num_drink += tuple_drink[i][1]
  else:
    sum += tuple_drink[i][0]*(M-num_drink)
    num_drink += M - num_drink
    break
print(sum) 

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

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  int D = A - B;
  vector<int> h(N);
  rep(i, 0, N) cin >> h[i];
  sort(h.begin(), h.end());
  ll left = 0, right = 1e9;
  while(right - left > 1) {
    ll mid = (left + right) / 2;
    int n = lower_bound(h.begin(), h.end(), B * mid + 1) - h.begin();
    ll cnt = mid;
    rep(j, n, N) {
      int v = h[j] - B * mid;
      cnt -= (v + D - 1) / D;
    }
    if(cnt >= 0) right = mid;
    else left = mid;
  }
  cout << right << endl;
  return 0;
}


Measured memory_bytes: 640
gp1=[1,3,5,7,8,10,12]
gp2=[4,6,9,11]

x,y=map(int,input().split())
if x in gp1 and y in gp1:
    print('Yes')
elif x in gp2 and y in gp2 :
    print('Yes')
elif x==y==2:
    print('Yes')
else:
    print('No')

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

#define endl "\n"
#define all(V) V.begin(),V.end()
#define see(x) cerr << #x << " = " << x << "\n";
#define Unique(V) sort(all(V)),V.erase(unique(all(V)),V.end())
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long int LL;
typedef pair <int,int> pii;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const double PI = acos(-1.0);
const long long INF = 1e18;
const int N = 100 + 5;

int n, cap;
LL w[ 105 ] , v[ 105 ];
LL dp[ 105 ][ 100005 ];

int main( ) {
        IO;
        cin >> n >> cap;
        for( int i = 1; i <= n; i++ ) cin >> w[i] >> v[i];
        for( int i = n; i >= 1; i-- ) {
                for( int c = cap; c >= 1; c-- ) {
                        if( w[i] <= c ) {
                                dp[i][c] = max( dp[i+1][c] , dp[i+1][c-w[i]] + v[i] );
                        }
                        if( i != n ) dp[i][c] = max( dp[i][c] , dp[i+1][c] );
                }
        }
        cout << dp[1][cap] << endl;
        return 0;
}









Measured memory_bytes: 79360
import java.util.*;
import java.io.*;

class Main{
    public static void main(String args[])throws IOException{
      try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
        String[] input = br.readLine().split(" ");
        
        int H = Integer.parseInt(input[0]);
        int A = Integer.parseInt(input[1]);
        int result = 0;

        while(H > 0){
          H = H - A;
          result++;
        }
    
        System.out.println(result);
      }
    }
}

Measured memory_bytes: 22996
//Keep Working Hard
  // I__Like__Food
  #include<bits/stdc++.h>
  #include <ext/pb_ds/assoc_container.hpp> 
  #include <ext/pb_ds/tree_policy.hpp>
  #pragma comment(linker, "/stack:200000000")
  #define rep(i,a,b) for(int i = a; i <=b; i++)
  #define rep2(i,a,b) for(int i = a; i>=b; i--)
  #pragma GCC optimize("O3")
  #pragma GCC optimize("Ofast") 
  #pragma GCC optimize("unroll-loops")
  using namespace std;
  using namespace __gnu_pbds;
  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define f first
  #define s second
  #define endl "\n"
  #define int long long
  #define all(v) v.begin(),v.end()
  #define PB push_back
  #define MP make_pair
  #define double long double
  #define trace1(x)                cerr<<#x<<": "<<x<<endl
  #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  #define cases int testcases;cin>>testcases; while(testcases--)
  #define MOD 998244353
  #define N 3005
  #define INF 1e16
  const double PI = acos(-1);

  double dp[N][N];
int32_t main()
{


    int n;
    cin >> n;

    double p[n+1];

    for(int i = 1; i <= n; i++)
    {
      cin >> p[i];
    }

    dp[0][0] = (double)1;
    // dp[i][j] denotes the required probability if i throw i coins and j heads
    for(int i = 1; i <= n; i++)
    {
      for(int j = 0;  j <= i; j++)
      {
        dp[i][j] = dp[i-1][j-1]*(p[i]) + dp[i-1][j]*(1-p[i]);
        // sum from either head or tail at ith throw
      }
    }


         double ans = 0;

         for(int i = 1; i <= n; i++)
         {
          if(i > n - i)
          {
            ans += dp[n][i];
          }
         }

         cout << fixed << setprecision(12) << ans;




  return 0;
  
}  

Measured memory_bytes: 139264
#include<iostream>

using namespace std;
int euclid(int n, int m);

int main(){
  int n,m;
  while(cin>>n>>m){
    cout <<euclid(n,m)<<endl;
  }
}

int euclid(int n,int m){
  if(n<m){
  int temp;
  temp=m;
  m=n;
  n=temp;
  }
  if(n%m==0){
    return m;
  }else{
    return euclid(m,n%m);
  }
}
  

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


int main(){
	int n;
	cin >> n;
	string s;
	int cntWA =0;
	int cntAC = 0;
	int cntTle = 0;
	int cntRE = 0;
	while(n--){
		cin >> s;
		if(s=="WA") cntWA++;
		else if (s=="AC") cntAC++;
		else if(s=="TLE") cntTle++;
		else cntRE++;
	}
	cout << "AC x " << cntAC << endl;
	cout << "WA x " << cntWA << endl;
	cout << "TLE x " << cntTle << endl;
	cout << "RE x " << cntRE << endl;
}

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

using namespace std;

const int N = 2e5 + 5;
vector<int> adj[N];
vector<int> sizes[N];
int sz[N];

int dfs(int node , int par) {
    sz[node] = 1;
    for (int child : adj[node]) {
        if (child != par) {
            sizes[node].push_back(dfs(child , node));
            sz[node] += sizes[node].back();
        }
    }
    return sz[node];
}

void dfs(int node , int par , int s) {
    if (node != 1)
        sizes[node].push_back(s);
    for (int child : adj[node])
        if (child != par)
            dfs(child , node , s + sz[node] - sz[child]);
}


const long long MOD = 1e9 + 7; // have to be a prime

long long mul(long long a , long long b) {
    return a * b % MOD;
}

int add (int a , int b) {
    a += b;
    while (a >= MOD) a -= MOD;
    while (a < 0) a += MOD;
    return a;
}

long long power(long long a , long long b) {
    if (!b) return 1;
    long long r = power(a , b / 2);
    r = mul(r , r);
    if (b&1) return mul(r , a);
    return r;
}

long long mod_inv(long long x) {
    return power(x , MOD - 2);
}


int main() {
    int n;
    cin >> n;
    for (int i = 0 ;i < n - 1 ;i++) {
        int u , v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1 , -1);
    dfs(1 , -1 , 0);

    int ans = 0;
    for (int i = 1 ;i <= n ;i++) {
        int zero = 1 , one = 0 , atleasttwo = 0;
        for (int x : sizes[i]) {
            int black = add(1 , -mod_inv(power(2 , x)));
            int white = add(1 , -black);
            atleasttwo = add(atleasttwo , mul(black , one));
            one = add(mul(one , white) , mul(zero , black));
            zero = mul(zero , white);
        }
        ans = add(ans , mul(atleasttwo , mod_inv(2)));
    }

    cout << ans;
}

Measured memory_bytes: 39652
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;

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

	vector<vector<pair<int, int>>> A(N);
	for (auto i = 0; i < N; ++i)
	{
		int a;
		cin >> a;
		for (auto j = 0; j < a; ++j)
		{
			int x, y;
			cin >> x >> y;
			A[i].push_back(make_pair(x - 1, y));
		}
	}

	auto result = 0;
	for (auto i = 0x07FFF; i >= 0; --i)
	{
		auto temp = 0;
		auto valid = true;
		for (auto j = 0; j < N; ++j)
		{
			auto honest = (i & (1 << j)) != 0;
			if (!honest)
			{
				continue;
			}

			++temp;

			for (auto& p : A[j])
			{
				auto truth = (i & (1 << p.first)) != 0;
				auto y = p.second;

				if (y != 0)
				{
					if (!truth)
					{
						valid = false;
						break;
					}
				}
				else
				{
					if (truth)
					{
						valid = false;
						break;
					}
				}
			}

			if (!valid)
			{
				temp = 0;
				break;
			}
		}

		result = max(result, temp);
	}

	cout << result << endl;

	return 0;
}

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

int main() {
  int N,M;
  cin>>N>>M;
  vector<int> a(M),b(M),count1(N),count2(N);
  rep(i,M){cin>>a[i]>>b[i];}
  rep(j,N){
    rep(i,M){
      if(a[i]==j+1){count1[j]++;}
      if(b[i]==j+1){count2[j]++;}
    }
    cout<<count1[j]+count2[j]<<endl;
  }
}

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

int main() {
  int N;
  cin >> N;
  vector<int> L(N);
  rep(i, N) cin >> L.at(i);

  int ans = 0;
  if (N < 3) {
    cout << ans << endl;
    return 0;
  }
  sort(L.begin(), L.end());

  int a, b, c;
  rep(i, N - 2) {
    a = L.at(i);
    for (int j = i + 1; j < N - 1; j++) {
      b = L.at(j);
      if (a == b) continue;
      for (int k = j + 1; k < N; k++) {
        c = L.at(k);
        if (a == c || b == c) continue;
        if (a + b <= c) break;
        ans++;
      }
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 3616
from bisect import bisect_left,bisect_right
n=int(input())
A=sorted(map(int,input().split()))
B=list(map(int,input().split()))
C=sorted(map(int,input().split()))
ans=0
for i in range(n):
    ans+=(bisect_left(A,B[i])*(n-bisect_right(C,B[i])))
print(ans)

Measured memory_bytes: 23360
// CppPractice.cpp : アプリケーションのエントリ ポイントを定義します。
//

//#include "stdafx.h"
#include <iostream>

using namespace std;

int main()
{
	int a,b;
	cin >> a >> b;

	if (a > b) {
		cout << "a > b" << endl;
	}
	else if (a < b) {
		cout << "a < b" << endl;
	}
	else {
		cout << "a == b" << endl;
	}
    return 0;
}




Measured memory_bytes: 3104
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char a[] = sc.next().toCharArray();
		for(int i=0;i<19;i++){
			if(a[i]==','){
				a[i]=' ';
			}
		}
		for(int i=0;i<19;i++){
			System.out.print(a[i]);
		}
	}
}


Measured memory_bytes: 21844
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
use std::io::*;
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::*;

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

//const MAX:usize = 100006;
//const INF:u64 = u64::max_value();

fn main() {
    let n:u32 = read();

    if n == 1 {
        println!("Hello World");
    } else {
        let a:i32 = read();
        let b:i32 = read();
        println!("{}", a+b);
    }

}


Measured memory_bytes: 4352
#include <iostream>
#include <stack>
#include <vector>
#include <string>
using namespace std;

int main()
{
	int n,p[10000],r[10000],pt[10000] = {0},rt[10000] = {0},j = 0,count = 0;

	while(1)
	{
		cin>>n;
		if(n == 0)break;

		count++;

		for(int i=0; i<n; i++){
			cin>>p[i]>>r[i];
			if(p[i] > r[i])
				pt[j] = pt[j] + p[i] + r[i];
			else if(p[i] < r[i])
				rt[j] = rt[j] + p[i] + r[i];
			else{
				pt[j] += p[i];
				rt[j] += r[i];
			}
		}
		j++;
	}
	for(int k=0; k<count; k++)
		cout<<pt[k]<<" "<<rt[k]<<endl;

	return 0;

}

Measured memory_bytes: 1320
#include <cmath>
#include <iostream>

int main() {

  int a;
  int b;
  int c;
  int d;
  int e;
  int k;
  std::cin >> a >> b >> c >> d >> e >> k;

  int ab = abs(a - b);
  int ac = abs(a - c);
  int ad = abs(a - d);
  int ae = abs(a - e);
  int bc = abs(b - c);
  int bd = abs(b - d);
  int be = abs(b - e);
  int cd = abs(c - d);
  int ce = abs(c - e);
  int de = abs(d - e);

  if (ab > k || ac > k || ad > k || ae > k || bc > k || bd > k ||
      be > k || cd > k || ce > k || de > k) {
    std::cout << ":(" << std::endl;
  } else {

    std::cout << "Yay!" << std::endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[200003],n;
map<int,int>built;
bool check(int num){
	built.clear();
	int l=0;
	for(int i=0;i<n;i++){
		if(a[i]>l)
			l=a[i];
		else{
			while(!built.empty()&&built.rbegin()->first>=a[i])built.erase(built.rbegin()->first);
			int c=a[i]-1; 
			built[c]++;
			while(built[c]>=num){
				built.erase(c);
				c--;
				built[c]++;
				if(c<0)return 0;
			}
			l=a[i];
		}
	}
	return 1;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	bool k=1;
	for(int i=1;i<n;i++)
		if(a[i]<=a[i-1])
			k=0;
	if(k){
		cout<<1;
		return 0;
	}
	int l=1,r=n+1;
	while(r>l+1){
		int mid=(l+r)/2;
		if(check(mid))
			r=mid;
		else
			l=mid;
	}
	cout<<r;
}

Measured memory_bytes: 1024
/*#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>*/
#include<bits/stdc++.h>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll, ll> P;
const ll mod = 1e9 + 7;
ll dx[4] = {1,0,-1,0};
ll dy[4] = {0,1,0,-1};

int main(){
    ll n,ans = 0,ret=1;
	cin >> n;
	rep(i,9){
		if(ret <= n) ans = ret;
		ret *= 2;
	}
	cout << ans << endl;
}  


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


int main() {
    int T;
    cin >> T;
    double e,f,a,b,c,d;
    while(T--) {
        cin >> e >> f >> a >> b >> c >> d;
        a -= e; c -= e;
        b -= f; d -= f;
        double den = 2 * (d * a - b * c);
        double y = a * (c * c + d * d) - c * (a * a + b * b);
        double x = b * (c * c + d * d) - d * (a * a + b * b);
        y /= den;
        x /= -den;
        printf("%.3lf %.3lf %.3lf\n", x + e, y + f, sqrt(x * x + y * y));
    }
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

constexpr int64 P = 998244353;

struct FiniteField {
 private:
  int64 x;
 public:
  FiniteField(int64 x) : x(x) {
    if (x > P || x < 0) { cerr << "Invalied FiniteField!" << endl; exit(1); }
  }
  FiniteField() : x(0) {}
  int64 Value() const { return x; }
  inline FiniteField operator+(FiniteField o) const {
    FiniteField r(*this); r += o; return r;
  }
  inline FiniteField operator-(FiniteField o) const {
    FiniteField r(*this); r -= o; return r;
  }
  inline FiniteField operator* (FiniteField o) const {
    FiniteField r(*this); r *= o; return r;
  }
  inline FiniteField operator/ (FiniteField o) const {
    FiniteField r(*this); r /= o; return r;
  }
  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }
  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }
  }
};

ostream& operator<<(ostream& s, const FiniteField& v) {
	s << v.Value(); return s;
}

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

  int n;
  cin >> n;
  vector<int> xs(n);
  int max_value = 0;
  for (int i = 0; i < n; i++) {
    cin >> xs[i];
    max_value = max(xs[i], max_value);
  }
  vector<int> cs(max_value + 1);
  for (int x : xs) cs[x]++;

  vector<FiniteField> ws(max_value + 1);
  for (int i = 1; i <= max_value; i++) {
    ws[i] = FiniteField(1) / i;
  }

  int count = 0;
  for (int i = 1; i <= max_value; i++) {
    for (int k = 2; i * k <= max_value; k++) {
      ws[i * k] -= ws[i];
      count++;
    }
  }

  FiniteField t = 0;
  for (int i = 1; i <= max_value; i++) {
    FiniteField s = 0;
    for (int k = 1; i * k <= max_value; k++) {
      s += FiniteField(i * k) * cs[i * k];
    }
    FiniteField inc = ws[i] * s * s;
    t += inc;
  }

  for (int x : xs) {
    t -= x;
  }
  t /= 2;

  cout << t.Value() << endl;
}

Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
double ab(double x,double y){
  if(x>y)
    return x-y;
  else
    return y-x;
}

int main(){
  int n,t,a,ans;
  cin >> n >> t >> a;
  vector<int> hi(n);
  for(int i=0;i<n;i++)
    cin >> hi[i];
  double oo=100000;
  for(int i=0;i<n;i++){
    double x;
    x=(double)t-0.006*hi[i];
    if(oo>ab(x,a)){
      oo=ab(x,a);
      ans=i;
    }
  }
  cout << ans+1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int a,b;
  cin >> a >> b;
  if((a+b)%2!=0){
    cout<<"IMPOSSIBLE"<<endl;
  }
  else {
    cout<< (a+b)/2<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string.h>

using namespace std;

#define _ABS(X) (((X) < 0) ? -(X) : (X))

char input[100005];
int ans[100005];

int main()
{
	scanf("%s", input);
	int len;
	int recent_R = 0;

	for (len = 1; input[len]; ++len)
	{
		if (input[len] == 'R') recent_R = len;
		else
		{
			int dist = len - (recent_R + 1);

			if (dist % 2 == 0) ans[recent_R + 1]++;
			else ans[recent_R]++;
		}
	}

	int recent_L = len - 1;

	for (int i = len - 2; i >= 0; --i)
	{
		if (input[i] == 'L') recent_L = i;
		else
		{
			int dist = (recent_L - 1) - i;

			if (dist % 2 == 0) ans[recent_L - 1]++;
			else ans[recent_L]++;
		}
	}

	for (int i = 0; i < len; ++i) printf("%d ", ans[i]);
	printf("\n");

	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define GET_ARRAY_SIZE(a)   (sizeof(a)/sizeof(a[0]))
#define LL long long
int main(){
    LL h,a,ans;
    cin >> h >> a;
    ans= h/a;
    if(h%a > 0) ans += 1;
    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main(int argc, const char * argv[]) {
    
    string stmp, stmp2;
    //vector<string> vs;
    /*
    while(true)
    {
        //char input = getchar();
        char input;
        cin.get(input);
        
        if(input == '0')
        {
            //vs.push_back("0");
            stmp.push_back('0');
        }
        else if(input == '1')
        {
            stmp.push_back('1');
        }
        else if(input == 'B')
        {
            stmp.pop_back();
        }
        
        cout << "\r" << stmp;
    }
    */
    cin >> stmp;
    for(int i = 0; i < stmp.size(); i++)
    {
        if(stmp[i] == 'B')
        {
            stmp2.pop_back();
        }
        else
        {
            stmp2.push_back(stmp[i]);
        }
    }
    cout << stmp2 << endl;
    return 0;
}

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

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a,b,c;
  string s,t;
  cin >>a>>b;
  cout <<max({a+b,a-b,a*b});
}

Measured memory_bytes: 3616
class Graph:
    class Edge:
        def __init__(self, to, cost):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost = to, cost

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges2 = []                            # ワーシャルフロイド用
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges2.append((x, y, cost))
        if self.directed == False:
            self.edges2.append((y, x, cost))     # ワーシャルフロイド用

    def warshall_folyd(self, INF=1<<30):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す
        """
        dist = [[INF] * self.n for _ in range(self.n)]

        for i, j, cost in self.edges2:
            dist[i][j] = cost
        for i in range(self.n):
            dist[i][i] = 0  # 自身のところに行くコストは０

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        return dist

    def warshall_folyd2(self, INF=1<<30):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す
        """
        dist = [[INF] * self.n for _ in range(self.n)]

        for i, j, cost in self.edges2:
            dist[i][j] = cost
            if dist[i][j] <= L:
                data.append((i, j))
        for i in range(self.n):
            dist[i][i] = 0

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        if dist[i][j] <= L:
                            data.append((i, j))
        return dist

def max2(x,y):
    return x if x > y else y

from itertools import combinations

N, M, L = map(int, input().split())
graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)

data = []
d = graph.warshall_folyd2()

graph2 = Graph(N, directed=False, decrement=False)
for i, j in combinations(range(N), 2):
    if d[i][j] <= L:
        graph2.add_edge(i, j, 1)


d = graph2.warshall_folyd()

for _ in range(int(input())):
    s, t, = map(int, input().split())
    s, t = s-1, t-1
    print(d[s][t]-1 if d[s][t] < 1<<20 else -1)

Measured memory_bytes: 554788
# A
S = int(input())


num = len(str(S))

min_num = 10**9

if S!=10**18:
    X1=0
    Y1=0

    X2 = S // min_num +1
    Y2 = X2*min_num - S

    X3 = 1
    Y3  = min_num

else:
    X1=0
    Y1=0

    X2 =10**9
    Y2 = 0

    X3 = 1
    Y3  = 10**9


print("{} {} {} {} {} {}".format(X1, Y1, X2, Y2, X3, Y3))

Measured memory_bytes: 3064
unittest
{
	assert( [ "12" ].solve == 1 );
	assert( [ "5" ].solve == 0 );
	assert( [ "1000000000000000000" ].solve == 124999999999999995 );
}

unittest
{
	// 追加ケース
	import std.algorithm;
	import std.bigint;
	BigInt test( long n )
	{
		if( n < 2 ) return BigInt( 1 );
		else        return n * test( n - 2 );
	}
	foreach( i; 0L .. 3001L )
	{
		auto k = test( i ).to!( string );
		assert( [ i.to!( string ) ].solve == k.length.signed - k.retro.find!( ( a ) => a != '0' ).walkLength );
	}
}



import std.conv;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	
	// 奇数の場合は末尾が0にならない
	if( n % 2 == 1 ) return 0L;
	
	// 素因数分解して2と5がセットにできる数だけ末尾の0が増える
	// 2はいっぱいあるので、5の数だけ数えれば良い
	auto ans = 0L;
	for( auto i = 10L; i <= n; i *= 5 )
	{
		ans += n / i;
	} 
	return ans;
}


Measured memory_bytes: 2764
#include <bits/stdc++.h>
typedef long long ll;
typedef double ld;
typedef unsigned long long ull;

using namespace std;

const int MX = 307;

ld f[MX + 5][MX + 5][MX + 5];

int main() {
    cin.sync_with_stdio(0), cin.tie(0);
    cout.sync_with_stdio(0), cout.tie(0);
    
    //freopen("demo.in", "r", stdin);
	//freopen("demo.out", "w", stdout);
	
    int n;
    cin >> n;
    int c1 = 0, c2 = 0, c3 = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        if (x == 1) c1++;
        else if (x == 2) c2++;
        else c3++;
    }

	/*
	
	*/
    for (int k = 0; k < MX; k++) {
        for (int j = 0; j + k < MX; j++) {
            for (int i = 0; i + j + k < MX; i++) {
                if (i + j + k == 0) continue;
                if (i + j + k > MX) continue;
                ld wait = 1.0 * n / (i + j + k);
                ld pi = 1.0 * i / (i + j + k);
                ld pj = 1.0 * j / (i + j + k);
                ld pk = 1.0 * k / (i + j + k);

                if (i) {
                    f[i][j][k] += pi * f[i - 1][j][k];
                }
                if (j) {
                    f[i][j][k] += pj * f[i + 1][j - 1][k];
                }
                if (k) {
                    f[i][j][k] += pk * f[i][j + 1][k - 1];
                }
                f[i][j][k] += wait;
            }
        }
    }

    cout.precision(11);
    cout << fixed << f[c1][c2][c3] << "\n";
    return 0;
}


Measured memory_bytes: 233728
// 23:10 - 23:
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
#define int long long
#define MOD 1000000007
typedef vector<int> vi;
typedef pair<int,int> pi;
#define inf 1e18
#define For(i,a,b) for (int i = a; i < b; i++)
#define Rep(i,a,b) for (int i = a; i <= b; i++)
#define ps(x,y) fixed << setprecision(y) << x 
#define pb push_back 
#define mp make_pair 
 
int32_t main()
{
    fast;
    int k, s, c = 0; cin >> k >> s;
    Rep(i, 0, k) {
        Rep(j, 0, k) {
            int m = s - i - j;
            if(m >= 0 and m <= k) ++c;
        }
    }
    cout << c;
    
    
    return 0;
}

Measured memory_bytes: 3648
from collections import Counter
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def inpl(): return list(map(int, input().split()))


N, a, b = inpl()
array = inpl()
value = Counter(array)
array.sort(reverse=True)
ans = {}
sum_a = 0
kosuu = 0
last = -1
# print("koko")
for i, num in enumerate(array):
    # print(i, num)
    sum_a += num
    if last != num:
        kosuu = 1
        last = num
    else:
        kosuu += 1
    if a <= i+1 <= b:
        ans[sum_a/(i+1)] = ans.get(sum_a/(i+1), 0) + cmb(value[num], kosuu)
print("{:.10f}".format(max(ans)))
print(int(ans[max(ans)]))

Measured memory_bytes: 3692
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

typedef long long ll;
int N,M,P;
ll D[2510];
bool negative[2510];
ll inf = 1e18;
struct edge {int from,to; ll cost;};

vector<edge> v;

void shortest_path(int s){
	for(int i=1;i<=N;i++) D[i] = inf;
	D[s] = 0;
	for(int j=0;j<N-1;j++){
		for(int i=0;i<v.size();i++){
			edge e = v[i];
			if(D[e.from] != inf && D[e.to] > D[e.from] + e.cost){
				D[e.to] = D[e.from] + e.cost;
			}
		}
	}
}

void find_negative_loop(){
	for(int i=1;i<=N;i++) negative[i] = false;
	for(int i=1;i<=N;i++){
		for(int j=0;j<v.size();j++){
			edge e = v[j];
			if(D[e.to]!=inf && D[e.to] > D[e.from] + e.cost){
				D[e.to] = D[e.from] + e.cost;
				negative[e.to] = true;
			}
			if(negative[e.from]) negative[e.to] = true;
		}
	}
}

int main(){
	cin >> N >> M >> P;
	for(int i=0;i<M;i++){
		int a,b,c;
		cin >> a >> b >> c;
		v.push_back((edge{a,b,P-c}));
	}
	shortest_path(1);
	ll ans = max(-D[N],0LL);
	find_negative_loop();
    cout << (negative[N]? -1:ans) << endl;
}

Measured memory_bytes: 3788