akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long
int inf = 10e17;
#define mod 1000000007
int findLowerBound(
    vector<pair<int, int>> &arr,
    pair<int, int> &p)
{

    auto low = lower_bound(arr.begin(),
                           arr.end(), p);

    return low - arr.begin();
}
int findUpperBound(
    vector<pair<int, int>> &arr,
    pair<int, int> &p)
{
    auto up = upper_bound(arr.begin(),
                          arr.end(), p);

    return up - arr.begin();
}
bool vis[200005];
vector<int> vec[2000005];
int child[2000005];
int parent[2000005];
int div1[100005];
void dfs(int node)
{
    vis[node] = 1;
    for (int i = 0; i < vec[node].size(); i++)
    {
        if (!vis[vec[node][i]])
        {
            parent[vec[node][i]] = node;
            dfs(vec[node][i]);
            //   child[node] += child[vec[node][i]];
        }
    }
}
void bfs(int node)
{
    queue<int> qu;
    qu.push(node);
    vis[1] = 1;
    while (!qu.empty())
    {
        int top = qu.front();
        //cout << qu.front() << "\n";
        qu.pop();
        vis[top] = 1;
        for (int i = 0; i < vec[top].size(); i++)
        {
            if (!vis[vec[top][i]])
            {
                parent[vec[top][i]] = top;
                qu.push(vec[top][i]);
                vis[vec[top][i]] = 1;
            }
        }
    }
}
void belman(int n, int m, vector<pair<int, pair<int, int>>> vec, int dis[])
{
    for (int i = 0; i <= n + m - 1; i++)
    {
        for (int j = 0; j < vec.size(); j++)
        {
            int u = vec[j].second.first;
            int v = vec[j].second.second;
            int w = vec[j].first;

            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
            }
        }
    }
}
int fun(int a, int b)
{
    if (a > b)
        return 0;
    if (a == b)
        return 1;
    else
    {
        return fun(a + 1, b) + fun(a, b - a);
    }
}
int32_t main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);

    int a, b;
    cin >> a >> b;
    if ((a + b) % 2)
    {
        cout << (a + b) / 2 + 1 << "\n";
    }
    else
    {
        cout << (a + b) / 2 << "\n";
    }

    return 0;
}


Measured memory_bytes: 50464
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

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

    ll n;
    cin >> n;

    ll a[n];
    map <ll, ll> mp;
    mp[0]++;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i) a[i] += a[i-1];
        mp[a[i]]++;
    }

    ll ans = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        ans += itr->second * (itr->second - 1) / 2;
    }

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

Measured memory_bytes: 14336
import std.stdio, std.conv, std.string, std.range, std.algorithm, std.array,
  std.functional, std.container, std.typecons;

alias Graph = int[][];

int c2(int n) {
  return (n * (n-1)) / 2;
}

void main() {
  auto input = readln.split.to!(int[]);
  int N = input[0], K = input[1];

  Graph G = new int[][N];
  int maxK = ((N-1) * (N-2)) / 2;
  if(K > maxK) {
    writeln(-1);
    return;
  }
  
  G[0] = iota(1, N).array;
  int num = maxK;
  outer: foreach(i; 1..N) {
    foreach(j; (1+i)..N) {
      if(num == K) break outer;
      G[i] ~= j;
      num--;
    }
  }

  auto M = G.map!"a.length".sum;
  M.writeln;
  foreach(i; 0..N) {
    foreach(j; G[i]) {
      writeln(i+1, " ", j+1);
    }
  }
}


Measured memory_bytes: 380
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
#define mem(a) memset(a,0,sizeof(a))
#define pd(a) printf("%.10f\n",a)
#define pb(a) push_back(a)
#define in(a) insert(a)
#define pi M_PI
#define R cin>>
#define F first
#define S second
#define C class
#define ll long long
#define ln cout<<'\n'
#define _(_1,_2,_3,N,...)N
#define pr(...) _(__VA_ARGS__,pr3,pr2,pr1)(__VA_ARGS__)
template<C T>void pr1(T a){cout<<a;ln;}
template<C T,C T2>void pr2(T a,T2 b){cout<<a<<' '<<b;ln;}
template<C T,C T2,C T3>void pr3(T a,T2 b,T3 c){cout<<a<<' '<<b<<' '<<c;ln;}
template<C T>void PR(T a,int n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
bool check(int n,int m,int x,int y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<60,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  int n,m;
  cin >> n >> m;
  vector<P> v[n];
  while(m--) {
    int x,y,z;
    cin >> x >> y >> z;
    v[x].pb(P(y,z));
  }
  int ans=MAX;
  rep(k,n) {
    int dp[1<<n][n];
    fill(dp[0],dp[1<<n],MAX);
    rep(i,v[k].size()) {
      int y=v[k][i].F;
      dp[1<<y][y]=v[k][i].S;
    }
    rep(t,1<<n) {
      rep(i,n) {
        rep(j,v[i].size()) {
          int y=v[i][j].F;
          if(t&(1<<y)) continue;
          dp[t|(1<<y)][y]=min(dp[t|(1<<y)][y],dp[t][i]+v[i][j].S);
        }
      }
    }
    ans=min(ans,dp[(1<<n)-1][k]);
  }
  if(ans==MAX) ans=-1;
  pr(ans);
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  Main();return 0;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
string s;
cin>>s;
ll arr[s.size()],sum=0;
for(int i=0;i<s.size();i++)
{
    ll x=(int)s[i]-48;
    arr[i]=x;
    sum+=arr[i];
}
if(sum%9==0)
cout<<"Yes\n";
else
cout<<"No\n";
}


Measured memory_bytes: 5312
import java.util.Scanner;

public class Main {
  public static int helper(String[] dataArr) {
    int minCount = 0;
    for (String number : dataArr) {
      int num = Integer.parseInt(number);
      int count = 0;
      while (num % 2 == 0) {
        num = num / 2;
        count++;
        if (minCount >= 1 && count >= minCount) break;
      }
      minCount = count;
      if (minCount == 0) return 0;
    }
    return minCount;
  }

  public static void main(String[] args) {
    Scanner dataScanner = new Scanner(System.in);
    dataScanner.nextLine();
    String data = dataScanner.nextLine();
    String[] dataArr = data.split(" ");
    int toOut = helper(dataArr);
    System.out.println(toOut);
  }
}

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

#define INF 1e9
#define MAX 100005
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define ull long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define nl '\n'
#define zai <<' '<<
#define all(a) a.begin(),a.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int n,m;
vi g[MAX];
int dp[MAX];
bool vis[MAX];
int ans=0;

void dfs(int u){
	vis[u]=true;
	for(auto v:g[u]){
		if(!vis[v]){
			dfs(v);
		}
		dp[u]=max(dp[u],dp[v]+1);
	}
}
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	int u,v;
	for(int i=0;i<m;i++){
		cin >> u >> v;
		g[u].pb(v);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[i]);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 8320
import java.util.Scanner;
 
public class Main{
 
    public static void main(String[] args) {
        Scanner s  = new Scanner(System.in);
        int N,x,t;
        N = s.nextInt();
        x = s.nextInt();
        t = s.nextInt();
        int count = 0;
        while(N>0){
            N = N-x;
            count++;
        }
        int result = count * t;
 
        System.out.println(result);
    }
}

Measured memory_bytes: 35612
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef vector<int> vec1;
typedef vector<string> vec2;
typedef vector<double> vec3;

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

  int a = s.size()-2;

  cout << s.at(0) << a << s.at(s.size()-1) << endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(" ").map(String::toInt)
    val h = readLine()!!.split(" ").map(String::toInt)
    var cnt = 0
    for ( i in 0 until n) {
        if (h[i] >= k) {
            cnt += 1
        }
    }
    println(cnt)
}

Measured memory_bytes: 47648
import java.util.*;
public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        String s = sc.next();
        int[] ls = new int[q];
        int[] rs = new int[q];
        for(int i = 0; i < q; i++) {
            ls[i] = sc.nextInt()-1;
            rs[i] = sc.nextInt()-1;

        }
        int count = 1;
        for(int i = 0; i < s.length()-1; i++) {
            if(s.charAt(i) == 'A' && s.charAt(i+1) == 'C') {
                map.put(i, count);
                count++;
            }
        }
        for(int i = 0; i < q; i++) {
            int start = ls[i];
            int end = rs[i];
            Integer start1 = map.ceilingKey(start);
            Integer start2 = map.floorKey(end-1);
            if(start1 == null || start2 == null) {
                System.out.println(0);
            } else {
                System.out.println(map.get(start2) - map.get(start1) + 1);
            }
        }
    }
}


Measured memory_bytes: 85544
#include <iostream>
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int,int>;
using ll = long long;


int main() {
    ll n,m;
    cin >> n >> m;
    vector<ll> h(n);
    vector<vector<int> > to(n);
    rep(i,n) cin >> h[i];
    int a,b;
    rep(i,m){
        cin >> a >> b;
        --a; --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    int count=0;
    rep(i,n){
        bool good=true;
        for(int u : to[i]){
            if(h[u]>=h[i]) good=false;
        }
        if(good) count++;
    }

    cout << count << endl;


}

Measured memory_bytes: 9000
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    BC = [list(map(int, input().split())) for _ in range(Q)]

    a = [0] * 100001
    for i in A:
        a[i] += i

    ans = sum(a)
    for b, c in BC:
        if a[b] == 0:
            print(ans)
            continue
        move = a[b] // b
        a[b] = 0
        a[c] += c * move
        ans += (c - b) * move
        print(ans)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 33900
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <list>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <iterator> 
#include <limits>

#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(A) (a).rbegin(),(a).rend()
#define PB push_back
#define MP make_pair

#define dump(x) cerr << #x << " = " << (x) << endl;

using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
//const int INF = numeric_limits<int>::max() / 2;
const double INF = numeric_limits<double>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

LL xs, ys, xt, yt;
int N;

const int MAX_V = 1000 + 10;
struct edge {int to; double cost; };
typedef pair<double, int> P; // (minimum distance, vertex id)
int V;
vector<edge> G[MAX_V];
double d[MAX_V];

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d + V, INF);
    d[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        // can't 'relax
        if (d[v] < p.first) {
            continue;
        }
        for (int i = 0; i < G[v].size(); i++) {
            edge e = G[v][i];
            // relax
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

double calc_distance(LL x1, LL y1, LL r1, LL x2, LL y2, LL r2) {
    double a = (x1 - x2) * (x1 - x2);
    double b = (y1 - y2) * (y1 - y2);
    double res = sqrt(a + b) - r1 - r2;
    if (res < 0) {
        res = 0;
    }
    return res;
}

vector<LL> X;
vector<LL> Y;
vector<LL> R;

int main(int argc, char const* argv[])
{
    cin >> xs >> ys >> xt >> yt;
    cin >> N;
    REP(i, N) {
        LL x, y, r;
        cin >> x >> y >> r;
        X.PB(x); Y.PB(y); R.PB(r);
    }
    REP(i, N) {
        REP(j, N) {
            if (i == j) {
                continue;
            }
            double dist = calc_distance(X[i], Y[i], R[i], X[j], Y[j], R[j]);
            edge e = edge{j, dist};
            G[i].PB(e);
        }
    }
    // from start(N)
    REP(i, N) {
        double dist = calc_distance(X[i], Y[i], R[i], xs, ys, 0);
        edge e = edge{i, dist};
        G[N].PB(e);
    }
    double dist = calc_distance(xs, ys, 0, xt, yt, 0);
    edge e = edge{N + 1, dist};
    G[N].PB(e);
    // to end(N + 1)
    REP(i, N) {
        double dist = calc_distance(X[i], Y[i], R[i], xt, yt, 0);
        edge e = edge{N + 1, dist};
        G[i].PB(e);
    }
    V = N + 2;
    dijkstra(N);
    /*
    REP(i, N + 2) {
        for (auto v : G[i]) {
            cout << i << " " << v.to << " " << v.cost << endl;
        }
    }
    */
    cout << setprecision(20) << d[N+1] << endl;
    return 0;
}


Measured memory_bytes: 20592
import math
MAX=510000
fac=[0]*MAX
finv=[0]*MAX
inv=[0]*MAX
MOD=10**9+7
#テーブルを作る前処理
def COMinit():
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,MAX):
      fac[i] = fac[i-1] * i % MOD
      inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
      finv[i] = finv[i - 1] * inv[i] % MOD

#二項係数計算
def comb(n,k):
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  else:
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

COMinit()
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
#print(A)
sum=0
for i in range(N-K+1):
  sum+=(A[N-1-i]-A[i])*(comb(N-i-1,K-1))%(10**9+7)
print(sum%(10**9+7))

Measured memory_bytes: 74584
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 100000000

struct edge {
	int to;
	int f;
	edge(int to_, int f_) {
		to = to_; f = f_;
	}
	edge(){}
};
struct status {
	int vertex;
	int cost;
	int c;
	status(int vertex_, int cost_, int c_) {
		vertex = vertex_; cost = cost_; c = c_;
	}
	status(){}
	bool operator<(const status & obj) const {
		if(this->c != obj.c)
			return this->c < obj.c;
		return this->cost > obj.cost;
	}
};

int main() {
	while(true) {
		int c, n, m, s, d;
		cin >> c >> n >> m >> s >> d;
		if(!(c || n || m || s || d))
			break;
		s--; d--;
		vector<vector<edge> > v(n);
		for(int i = 0; i < m; i++) {
			int a, b, f;
			cin >> a >> b >> f;
			a--; b--;
			v[a].push_back(edge(b,f));
			v[b].push_back(edge(a,f));
		}
		priority_queue<status> q;
		int cost[128][16];
		for(int i = 0; i < 128; i++)
			for(int j = 0; j < 16; j++)
				cost[i][j] = INF;
		q.push(status(s, 0, c));
		while(!q.empty()) {
			status cur;
			cur = q.top(); q.pop();

			if(cost[cur.vertex][cur.c] == INF) {
				cost[cur.vertex][cur.c] = cur.cost;
				for(int i = 0; i < v[cur.vertex].size(); i++) {
					if(cost[v[cur.vertex][i].to][cur.c] == INF) {
						q.push(status(v[cur.vertex][i].to, v[cur.vertex][i].f + cur.cost, cur.c));
					}
					if(cur.c > 0 && cost[v[cur.vertex][i].to][cur.c-1] == INF) {
						q.push(status(v[cur.vertex][i].to, v[cur.vertex][i].f / 2 + cur.cost, cur.c - 1));
					}
				}
			}
		}

		int ret = INF;
		for(int i = 0; i <= c; i++) {
			ret = min(ret, cost[d][i]);
		}
		cout << ret << endl;
	}
}

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

int n,k,sum;
string s;

int main()
{
	int i;
	cin>>n>>k>>s;
	sum=n-1;
	for (i=1;i<n;i++)
	{
		sum-=(s[i]!=s[i-1]);
	}
	sum=min(n-1,sum+k*2);
	cout<<sum<<endl;
	return 0;
}

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

typedef long long ll;
const ll N = 1e5 + 100, inF = 1e17;
ll A, B, C, n, a[N], b[N], c[N], dex[N], up[N], down[N];

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> A >> B >> C;
	n = A + B + C;
	for (int i = 0; i < n; i++)
		cin >> a[i] >> b[i] >> c[i];
	iota(dex, dex + n, 0);
	sort(dex, dex + n, [](int x, int y) {
		return c[x] - b[x] < c[y] - b[y];
	});
	// a - b
	fill(up, up + N, -inF);
	multiset<ll> st;
	ll now = 0;
	for (int i = 0; i < B; i++) {
		int ind = dex[i];
		st.insert(a[ind] - b[ind]);
		now += b[ind];
	}
	if(B)
		up[B - 1] = now;
	for (int i = B; i < n; i++) {
		int ind = dex[i];
		if(B == 0) {
			now += a[ind];
			up[i] = now;
			continue;
		}
		if(a[ind] - b[ind] > (*st.rbegin()))
			now += a[ind];
		else {
			ll val = *st.rbegin();
			st.erase(st.find(val));
			now += val;
			now += b[ind];
			st.insert(a[ind] - b[ind]);
		}
		up[i] = now;
	}
	// a - c
	fill(down, down + N, -inF);
	st.clear();
	now = 0;
	for (int i = 0; i < C; i++) {
		int ind = dex[n - i -1];
		st.insert(a[ind] - c[ind]);
		now += c[ind];
	}
	down[n - C] = now;
	for (int i = C; i < n; i++) {
		int ind = dex[n - i - 1];
		if(C == 0) {
			now += a[ind];
			down[i] = now;
			continue;
		}
		if(a[ind] - c[ind] > (*st.rbegin()))
			now += a[ind];
		else {
			ll val = *st.rbegin();
			st.erase(st.find(val));
			now += val;
			now += c[ind];
			st.insert(a[ind] - c[ind]);
		}
		down[n - i - 1] = now;
	}
	ll ans = 0;
	for (int i = 0; i < n - 1; i++)
		ans = max(ans, up[i] + down[i + 1]);
	cout << ans;
	return 0;
}

Measured memory_bytes: 9344
N=int(input())
T= [list(map(int,input().split())) for _ in range(N)]

is_able=True
pre_t = 0
pre_x = 0
pre_y = 0
for i in range(len(T)):
  if (T[i][0] % 2) != (T[i][1]+T[i][2])%2:
    is_able=False
    break
  if T[i][0]-pre_t < (T[i][1]-pre_x + T[i][2]-pre_y):
    is_able=False
    break
  pre_t=T[i][0]
  pre_x=T[i][1]
  pre_y=T[i][2]
if is_able:
  print('Yes')
else:
  print('No')
  

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

int main(){
    int r, g, b;
    cin >> r >> g >> b;
    int ans = r*100+g*10+b;
    if(ans % 4 == 0) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
//by Top1
#include <bits/stdc++.h>
          
#define f first
#define s second
#define int long long
#define ld long double
#define ull unsigned long long
#define pii pair <int, int>
#define pll pair <long, long>
#define mp make_pair
#define pb push_back
#define pf push_front
#define pp pop_back
#define cerr cout
#define rev reverse
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define forn(i, a, b) for (int i = a; i <= b; i++)
#define boost ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0);
#define nxtp next_permutation
#define pvtp prev_permutation
#define KZ return 
#define x1 x21212121
#define y1 y21212121
#define sqr(x) x * x 
      
const int inf = (1e9) + 1;
const int mod = 479001599;
const int maxn = 2e3 + 11;
        
using namespace std;          

int n, dp[maxn][maxn], mx;
pii a[maxn];


void solve(){   
	cin >> n;

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

	sort(a + 1, a + n + 1);
	rev(a + 1, a + n + 1);


	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= i; j++){
			dp[j][i - j] = max(dp[j][i - j], dp[j - 1][i - j] + a[i].f * abs(j - a[i].s));
			dp[i - j][j] = max(dp[i - j][j], dp[i - j][j - 1] + a[i].f * abs(n - j + 1 - a[i].s));
			mx = max(mx, max(dp[j][i - j], dp[i - j][j]));
		}
	}

	cout << mx;
}                              
      
main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

    boost;
    
    int q = 1;
 
    //cin >> q;
    
    while (q--){
        solve();
    }
}

Measured memory_bytes: 26296
#include <iostream>

using namespace std;

int main(){
  int N;

  while(cin >> N, N){
    int x,y,z,w;
    int x1,y1,z1,w1,x2,y2,z2,w2;
    for(int i = 0 ; i < N ; i++){
      cin >> x1 >> y1 >> z1 >> w1 >> x2 >> y2 >> z2 >> w2;
      x = x1*x2-y1*y2-z1*z2-w1*w2;
      y = x1*y2+x2*y1+z1*w2-w1*z2;
      z = x1*z2-y1*w2+x2*z1+w1*y2;
      w = x1*w2+y1*z2-z1*y2+w1*x2;
      cout << x << " " << y << " " << z << " " << w << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 1160
import java.util.*;

public class Main {
	public static void main ( String args[] ) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for ( int i = 0; i < n; i++ ) {
			double x1 , y1 , x2 , y2 , x3 , y3 , x4 , y4;
			x1 = sc.nextDouble();
			y1 = sc.nextDouble();
			x2 = sc.nextDouble();
			y2 = sc.nextDouble();
			x3 = sc.nextDouble();
			y3 = sc.nextDouble();
			x4 = sc.nextDouble();
			y4 = sc.nextDouble();
			if ( (( y1-y2 ) / ( x1-x2 )) == (( y3-y4 ) / ( x3-x4 )) )
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}
}

Measured memory_bytes: 12000
n, k = map(int, input().split())
a = list(map(int, input().split()))

# 約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

ans = 1

for div in make_divisors(sum(a)):
    mod_div = []
    for ai in a:
        mod_div.append(ai % div)
    mod_div.sort()

    tmp_p = n * div - sum(mod_div)
    tmp_m = 0

    for i, x in enumerate(mod_div):
        tmp_m += x
        tmp_p -= div - x
        if tmp_m == tmp_p and tmp_m <= k:
            ans = max(div, ans)

print(ans)


Measured memory_bytes: 41948
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            long a = in.nextLong();
            long b = in.nextLong();
            long c = in.nextLong();
            long d = in.nextLong();

            long max = (long) -1e18;
            max = Math.max(max, a * c);
            max = Math.max(max, a * d);
            max = Math.max(max, b * c);
            max = Math.max(max, b * d);
            System.out.println(max);
        }
    }
}


Measured memory_bytes: 27076
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>

using namespace std;
#define vsort(v) sort(v.begin(), v.end());
#define vunique(v) unique(v.begin(), v.end());

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string S;
	cin >> S;
	S[3] = '8';
	cout << S << endl;
}


Measured memory_bytes: 256
if __name__ == '__main__':
    s = input().rstrip().split(' ')
    K = int(s[0])
    N = int(s[1])
    s = input().rstrip().split(' ')
    A = [int(elem) for elem in s]
    B = [[0,0] for elem in s]
    for i in range(len(A)-1):
        B[i][0] = abs(A[i]-A[i+1])
        B[i+1][1] = abs(A[i]-A[i+1])

    B[len(A)-1][0] = K-abs(A[len(A)-1]-A[0])
    B[0][1] = K-abs(A[len(A)-1]-A[0])

    ans = float('inf')

    for elem in B:
        if(ans > K-elem[0]):
            ans = K-elem[0]
        if(ans > K-elem[1]):
            ans = K-elem[1]

    print(ans)


Measured memory_bytes: 45628
function main()
  N,K=map(x->parse(Int,x),split(readline()))
  vis=[false for _=1:N]
  for _=1:N
    readline()
    for a=map(x->parse(Int,x),split(readline()))
      if !vis[a]
        vis[a]=true
        N-=1
      end
    end
  end
  println(N)
end
main()

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

#define f first
#define s second
#define pb push_back

#define ll long long

#define mp make_pair

#define int ll

using namespace std;
                        

const int inf = 1e9 + 7;

const ll ll_inf = 1e18 + 7;
const int K = 18;
const int N = 3e5 + 100;
                        

ll binpow (ll a, ll n)
{
    ll res = 1;
    while (n) {
        if (n & 1)
        {
            res *= a;
            res %= inf;
        }
        a *= a;
        n >>= 1;
        a %= inf;
    }                      	
    return res;
}   

void boost()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

int sum;

int n,m;

int a[200];

main()
{
	cin >> n >> m;
	for (int i = 1;i <= n;++i)
	{
		cin >> a[i];
		sum += a[i];
	}
	sum = (sum / (4 * m)) + min(1ll,(sum % (4 * m)));
	int kol = 0;
	for (int i = 1;i <= n;++i)
	{
	   	if (sum <= a[i])
	   		kol++;
	}
	if (kol >= m)
	{
		cout << "Yes";
	}
	else
		cout << "No";

}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
namespace aizu
{
    class OnlineJudge
    {
        static void Main()
        {
            Dictionary<string, int> words = new Dictionary<string, int>();
            Console.ReadLine().Split().ToList().ForEach(word => {
                if(!words.ContainsKey(word)) {
                    words.Add(word, 0);
                }
                ++words[word];
            });
            Console.WriteLine("{0} {1}", words.OrderBy(i => i.Value).Last().Key, words.OrderBy(i => i.Key.Length).Last().Key);
            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 6312
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#define ALL(v) begin(v),end(v)
#else
#define ALL(v) (v).begin(),(v).end()
#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8


void mainmain(){
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	int a = tx - sx, b = ty - sy;
	cout << 'D' << string(a + 1, 'R') << string(b + 1, 'U') << 'L';
	cout << string(b, 'D') << string(a, 'L');
	cout << string(b, 'U') << string(a, 'R');
	cout << 'U' << string(a + 1, 'L') << string(b + 1, 'D') << "R\n";
}



}
int main() try{
//	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	cerr << fixed << setprecision(4);
	mainmain();
}
catch(...){}


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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    long long int n,i,j,k,l;
    string s="ACL",p="";
    cin>>n;
    for(i=0;i<n;i++)
     p=p+s;
     cout<<p;
     
    




    return 0;
}

Measured memory_bytes: 3656
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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;
}

using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1e17;
#define int long long

int cnt[55][30];
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	rep(i, n) {
		string s; cin >> s;
		rep(j, s.size()) {
			cnt[i][s.at(j) - 'a']++;
		}
	}
	rep(i, 30) {
		bool ok = true;
		int now = cnt[0][i];
		rep(j, n) {
			chmin(now, cnt[j][i]);
		}
		if (ok) {
			rep(j, now) {
				cout << (char)('a' + i);
			}
		}
	}
	cout << endl;
	return 0;
}


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;
int main(void){
   int N;
   cin>>N;
   int odd=N/2;
   if(N%2==1){
       odd++;
   }
   
   double ans=(double)odd/N;
   cout<<fixed<<setprecision(6);
   cout<<ans<<endl;
}


Measured memory_bytes: 3768
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 998244353;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned long long ULL;
//typedef boost::multiprecision::cpp_int bigint;

template<class T>
struct Gedge {
	LL src, to;
	T cost;
	Gedge(LL s, LL t, T c) :src(s), to(t), cost(c) {}
	Gedge(LL t, T c) :src(-1), to(t), cost(c) {}
};

template<class T>
using WeightedGraph = vector<vector<Gedge<T>>>;
using UnweightedGraph = vector<vector<LL>>;
template<class T>
using Gedges = vector<Gedge<T>>;

struct TNode {
	LL parent;
	VLL childs;
	TNode() :parent(-1) {};
};
using Tree = vector<TNode>;

//到達不可能->INF
template<class T>
void dijkstra(WeightedGraph<T>& G, LL start, vector<T>& res) {
	res.resize(G.size(), INF);
	res[start] = 0;
	typedef pair<T, LL> P;
	priority_queue<P, vector<P>, greater<P>> q;
	q.push(P(0, start));
	while (!q.empty()) {
		LL cur = q.top().second;
		T cost = q.top().first;
		q.pop();
		if (res[cur] < cost)continue;
		for (Gedge<T> e : G[cur]) {
			if (res[e.to] > cost + e.cost) {
				res[e.to] = cost + e.cost;
				q.push(P(res[e.to], e.to));
			}
		}
	}
	return;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	LL N, M, S, T;
	cin >> N >> M >> S >> T;
	S--; T--;
	WeightedGraph<LL> GA(N),GB(N);   //円、すぬーく
	for (LL m = 0; m < M; m++) {
		LL u, v, a, b;
		cin >> u >> v >> a >> b;
		u--; v--;
		GA[u].push_back({ u,v,a });
		GA[v].push_back({ v,u,a });
		GB[u].push_back({ u,v,b });
		GB[v].push_back({ v,u,b });
	}
	VLL resa, resb;
	dijkstra(GA, S, resa);
	dijkstra(GB, T, resb);
	VLL ans(N);
	ans.back() = resa.back() + resb.back();
	for (LL n = N - 2; n >= 0; n--) {
		LL temp = resa[n] + resb[n];
		ans[n] = min(ans[n + 1], temp);
	}
	for (LL n = 0; n < N; n++)cout << ((LL)1e15-ans[n]) << "\n";
	return 0;
}


Measured memory_bytes: 21832
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
// template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n ; cin  >> n;
    n %= 10;
    if (n == 2 || n == 4 || n == 5 || n == 7 || n == 9) cout << "hon\n";
    else if (n == 3) cout << "bon\n";
    else cout << "pon\n";
    return 0;
}

Measured memory_bytes: 3648
#include <stdio.h>
int main(void){
    char A[10],B[10],C[10],a,b;
    int n;
    scanf("%s%s%s",A,B,C);
    for(n=0;n<=10;n++){
        if(A[n]=='\0'){a=A[n-1]; break;}
    }
    for(n=0;n<=10;n++){
        if(B[n]=='\0'){b=B[n-1]; break;}
    }
    if(a==B[0]&&b==C[0]) printf("YES\n");
    else printf("NO\n");
    return 0;
}


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

int main(){
  int N;
  cin>>N;
  int A[N];
  int B[N];
  for(int i=0;i<N;i++){
    cin>>A[i];
    B[i]=A[i];
  }
  sort(A,A+N);
  reverse(A,A+N);
  for(int i=0;i<N;i++){
    if(B[i]==A[0]){
      cout<<A[1]<<endl;
    }else{
      cout<<A[0]<<endl;
    }
  }
}

Measured memory_bytes: 5204
from sys import stdin
def main():
  readline = stdin.readline
  N = int(readline())
  L = [list(map(int, readline().split())) for _ in range(N)]
  cnt = 0
  for l in L[::-1]:
    a = l[0]
    if a == 0:
      continue
    a += cnt
    b = l[1]
    if a <= b:
      cnt += b - a
    else:
      cnt += (b - a % b) % b
  print(cnt)
if __name__ == "__main__":
  main()

Measured memory_bytes: 27932
#include <bits/stdc++.h>
#define LL long long
#define lowbit(x) (x&(-x))
#define INF 0x7FFFFFFF//or 0x3f3f3f3f ?
using namespace std;

template<class T> inline
void read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}

/*============ Header Template ============*/

const int N = 1000000 + 5;

int n;
int mx[N][26];
int vis[N];
char S[N], T[N];
queue<int> Q;

int main() {
    // freopen("you.in", "r", stdin);
    // freopen("you.out", "w", stdout);
    read(n);
    scanf("%s", S + 1);
    scanf("%s", T + 1);
    int flag = 1;
    for (int i = 1; i <= n; i++) if (S[i] != T[i]) flag = 0;
    if (flag) {
        printf("0\n");
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 26; j++) mx[i][j] = mx[i - 1][j];
        mx[i][S[i] - 'a'] = i;
    }
    int pos = n + 1, ANS = 0, cnt = 0;
    for (int i = n; i; i--) {
        if (T[i] == T[i - 1]) continue; cnt++;
        int tmp = mx[min(i, pos - 1)][T[i] - 'a'];
        if (tmp == 0) {
            printf("-1\n");
            return 0;
        }
        while (!Q.empty()) {
            int x = Q.front();
            if (x - (cnt - vis[x] - 1) > i) Q.pop();
            else break;
        }
        if (!Q.empty()) {
            int x = Q.front();
            ANS = max(ANS, (cnt - vis[x]) + 2);
        } else ANS = max(ANS, (i == tmp ? 1 : 2));
        if (tmp != i) {Q.push(tmp); vis[tmp] = cnt;}
        pos = tmp;
    }
    // cerr << ans << endl;
    printf("%d\n", ANS);
    return 0;
}

Measured memory_bytes: 111744
N = int(input())
src = [int(input()) for i in range(N)]
idx = {a:i for i,a in enumerate(src)}

size = [1] * N
ss = list(sorted(src))

es = []
while len(ss) > 1:
    a = ss.pop()
    k = size[idx[a]]
    b = a + 2*k - N
    if b == a or b not in idx:
        print(-1)
        exit()
    size[idx[b]] += k
    es.append((idx[a],idx[b]))

gr = [[] for i in range(N)]
for a,b in es:
    gr[a].append(b)
    gr[b].append(a)

from collections import deque
dist = [N] * N
dist[idx[ss[0]]] = 0
q = deque([idx[ss[0]]])
while q:
    v = q.popleft()
    for to in gr[v]:
        if dist[to] < N: continue
        q.append(to)
        dist[to] = dist[v] + 1

if all(d<N for d in dist) and sum(dist) == ss[0]:
    for a,b in es:
        print(a+1, b+1)
else:
    print(-1)

Measured memory_bytes: 44884
import math, sys

N,K = map(int,input().split())
A = [int(x) for x in input().split()]
lower = 0
upper = 10**10

while upper - lower > 0.1:
    cuts = 0
    trial = (lower + upper) / 2
    for i in A:
        cuts += math.ceil(i/trial)-1
    if cuts <= K:
        upper = trial
    else:
        lower = trial
ans = math.ceil(lower)
if ans == 0:
    print(1)
    sys.exit()
cuts = 0
for i in A:
    cuts += math.ceil(i / ans) - 1
if cuts <= K: print(ans)
else: print(ans + 1)

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

#define froop1(a,n) for(int i = a;i < n;i++)
#define froop2(a,n) for(int i = a;i > n;i--)
int main(){
	string N;
  vector<string> b;
  cin >> N;
  int t = 1;
  for(int i = N.length() - 1;i >= 0;i--){
	if(N.substr(i,t) == "dream" || N.substr(i,t) == "dreamer" || N.substr(i,t) == "erase" || N.substr(i,t) == "eraser"){
		b.push_back(N.substr(i,t));
      t = 0;
    }
    if(t >= 7)break;
    t++;
  }
string check = "";
  for(int i = b.size() - 1;i >= 0;i--){
      check += b.at(i);
  }
  if(N == check){
   cout <<  "YES";
  }else{
	cout <<	"NO";
  }
  cout << endl;
return 0;
}

Measured memory_bytes: 4456
import java.util.Scanner;

public class Main 
{
	static int n, m, k;
	static int[] par;
	static int[] rank;
	
	static void union(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		
		if(rank[rx] >= rank[ry])
		{
			par[ry] = rx;
			if(rank[rx] == rank[ry])
				rank[rx]++;
		}
		else par[rx] = ry;
	}
	
	static int root(int x)
	{
		if(par[x] != x)
			par[x] = root(par[x]);
		return par[x];
	}
	
	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(); //par
		int m = sc.nextInt(); //lang
		par = new int[n + m];
		rank = new int[n + m];
		for(int i = 0; i < n+m;i++)
			par[i] = i;
		
		for(int i = 0; i < n; i++)
		{
			int l = sc.nextInt();
			for(int k = 0; k < l; k++)
			{
				int lan = sc.nextInt()-1;
				union(i,n+lan);
			}
		}	
		
		int root = root(0);
		for(int i = 1; i<n; i++)
		{
			if(root != root(i))
			{
				System.out.println("NO");
				return;
			}
		}

		System.out.println("YES");
	}

}


Measured memory_bytes: 66264
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,a,b) for (int i = (b-1); i >= (a); i--)
#define REP(i,n) FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const ll mod = 1e9+7;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

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;}

int main () {
  int K, S; cin >> K >> S;

  int ans = 0;
  REP(X,K+1) {
    REP(Y,K+1) {
      int Z = S-(X+Y);
      if (0<=Z && Z <= K) ans++;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
#include<map>
#include<deque>
#include<cstdio>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define ll __int64
#define __int64 long long
#define P pair<int,int>
#define PP pair<P,int>

int n,q;
string s;

struct SegmentTree {
private:
    int n;
    vector<int> node;

public:
    SegmentTree(int hoge) {
        int sz = hoge;
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, 0);
        for(int i=0; i<sz; i++) node[i+n-1] = 1<<((int)(s[i]-'a'));
        for(int i=n-2; i>=0; i--) node[i] = node[2*i+1] | node[2*i+2];
    }

    void update(int x,char val) {
        x += (n - 1);
        node[x] = 1<<((int)(val-'a'));
        while(x > 0) {
            x = (x - 1) / 2;
            node[x] = node[2*x+1] | node[2*x+2];
        }
    }

    int get(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        if(r <= a || b <= l) return 0;
        if(a <= l && r <= b) return node[k];

        int vl = get(a, b, 2*k+1, l, (l+r)/2);
        int vr = get(a, b, 2*k+2, (l+r)/2, r);
        return vl |  vr;
    }
};

int main() {
    cin>>n>>s>>q;
    SegmentTree seg(n);
    rep(i,q){
        int a;
        cin>>a;
        if(a==1){
            int b;
            char x;
            cin>>b>>x;
            seg.update(b-1,x);
        }
        else{
            int l,r;
            cin>>l>>r;
            l--;r--;
            int ret=seg.get(l,r+1);
            int ans=0;
            rep(j,26)if(ret&(1<<j))ans++;
            cout<<ans<<endl;
        }

    }
    return 0;
}

Measured memory_bytes: 4996
#include<bits/stdc++.h>
using namespace std;
int n[4][3][10];
int main(){
int x,b,f,r,v;
cin>>x;
for(int c=0;c<x;c++)
	{cin>>b>>f>>r>>v;
	n[b-1][f-1][r-1]+=v;};
for(int c=0;1;c++)
	{for(int c2=0;c2<3;c2++)
		{for(int c3=0;c3<10;c3++)
			{cout<<" "<<n[c][c2][c3];
			};
		cout<<endl;
		};
	if(c==3) break;
	cout<<"####################"<<endl;
	};
return 0;
}


Measured memory_bytes: 3080
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a,b):
    return a * b / gcd(a, b)

n = input()
t = []
for i in range(n):
    t.append(input())

key = t.pop(0)

while len(t) != 0:
    b = t.pop(0)
    key = lcm(key, b)

print key


Measured memory_bytes: 2820
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <complex>
#include <cmath>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,b) FOR(i,0,b)
#define X real()
#define Y imag()
using namespace std;
typedef complex<int> cld;
typedef vector<cld> vcl;
typedef vector<int> vi; 
const cld imagine=cld(0,1);

int main() {
	int n,m,win,lose;
	while(cin >> n >> m && n){
	vi lower[5001];
	int loseTimes[5001]={};
	int rank[5001]={};
	REP(i,m){
		cin >> win >>lose;
		lose-=1;
		win-=1;
		lower[win].push_back(lose);
		loseTimes[lose]++;
	}
	queue<int> qu;
	REP(i,n)
		if(loseTimes[i]==0)
			qu.push(i);
	while(!qu.empty()){
		int tar=qu.front();
		qu.pop();
		cout <<tar+1 << endl;
		REP(i,lower[tar].size()){
			int next=lower[tar][i];
			loseTimes[next]--;
			if(loseTimes[next]==0){
				qu.push(next);
				rank[next]=rank[tar]+1;
			}
		}
	}
	int maxim=0;
	REP(i,n)
	maxim=max(maxim,rank[i]);
	cout << (maxim+1!=n) << endl;
}
	// your code goes here
	return 0;
}

Measured memory_bytes: 1928
#include<bits/stdc++.h>
#define _USE_MATH_DEFINES
using namespace std;
    
#define ll long long int
#define pb push_back
#define rep(i , j , n) for(ll i = j ; i < n ; i++)
#define pre(i , j , n) for(ll i = j ; i >= n ; i--)
#define all(x) x.begin(), x.end()
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vll;
typedef vector<char>	vc;
typedef vector<bool>	vb;
typedef pair<ll,ll> 	pll;
#define br "\n"
#define ff first
#define ss second
#define MAXIM 1000003

ll mod = 1e9 + 7;


void solve(){ 
    string s;
    cin >> s;
    if(s.back() != 's') cout << s + 's' << br;
    else cout << s + "es" << br;
}
	

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif 

	ll t = 1;
	// cin >> t;
	rep(i,0,t){
		solve();
	}
 
}	

Measured memory_bytes: 3600
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq
logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)

MOD = 10**9+7

def main():
    N=int(input())
    odd=0
    for i in range(1,N+1):
        if i % 2 == 1:
            odd+=1
    print(odd*1.0/N)
main()

Measured memory_bytes: 68844