akhauriyash/Code-Regression huggingface dataset:
N = int(input())
D,X = map(int,input().split())
lists = []
day_list = []
chocolate = 0
for i in range(N):
        A = int(input())
        lists.append(A)
        day_list = []
        for j in range(D):
                if j*lists[i]+1 <= D:
                        day_list.append(j*lists[i]+1) 
                
        chocolate += len(day_list)
print(X+chocolate)

Measured memory_bytes: 3060
"use strict"
const create = () => {
    const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
    const res = {
        "list": input, "index": 0, "max": input.length,
        "hasNext": function () { return this.index < this.max },
        "next": function () { if (!this.hasNext()) { throw "ArrayIndexOutOfBoundsException"; } else { return this.list[this.index++]; } }
    };
    return res;
}
const o = create();
const next = () => o.next()
const nextInt = () => parseInt(o.next())
const nextStrArray = () => o.next().split(" ")
const nextIntArray = () => o.next().split(" ").map(el => parseInt(el))
const nextCharArray = () => o.next().split("")
const hasNext = () => o.hasNext()
const myout = (...x) => console.log(...x)
const Main = () => {
    const [N, Y] = nextIntArray()
    const isMatched = (a, b, c) => {
        return a >= 0 && b >= 0 && c >= 0 && a + b + c == N && 10000 * a + 5000 * b + 1000 * c == Y
    }
    let aMax = Math.ceil(Y / 10000)
    let bMax = Math.ceil(Y / 5000)
    for (let na = 0; na <= aMax; na++) {
        for (let nb = 0; nb <= bMax; nb++) {
            let nc = N - na - nb
            if (isMatched(na, nb, nc)) {
                console.log(na, nb, nc)
                return
            }
        }
    }
    console.log(-1, -1, -1)
}
Main()

Measured memory_bytes: 31856
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define pb push_back
#define f first
#define s second
using namespace std;


ll gcd(ll a, ll b)   //Function to find gcd of two numbers
{
    if (a == 0)
    return b;
    return gcd(b % a, a);
}

struct UnionFind{
  
   vector<int>parent;

   UnionFind(int n)
   { 
       parent = vector<int>(n,-1);

   }

//Find the parent using path compression
   int Find(int x)
   {
       if(parent[x]<0)
       return x;
       
       return parent[x] = Find(parent[x]);
   }
   
   bool Union(int x , int y)
   {
       int x_rep = Find(x);
       int y_rep = Find(y);

       if(x_rep==y_rep)
       return false;
       
       if(parent[x_rep] > parent[y_rep])
       swap(x_rep,y_rep);

       parent[x_rep]+=parent[y_rep];

       parent[y_rep] = x_rep;

       return true;
   }

   int Size(int x)
   {
       return -parent[Find(x)];
   }

};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n,m;
    cin>>n>>m;

    //makefriends
    UnionFind UF(n);

    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;

        u--;v--;

        UF.Union(u,v);
    }

    //Find the maximum friends-set
    int ans=0;

    for(int i=0;i<n;i++)
    {
        ans = max(ans,UF.Size(i));
    }

    cout<<ans<<endl;

    return 0;
}

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

long long dp[3001][3001][3];
const long long MOD = 998244353;

long long sum_mod (int x, int y) {
	if (x + y < MOD)
		return x + y;
	return x + y - MOD;
}

signed main () {
	int n, s;
	cin >> n >> s;
	vector < int > a(n);
	for (int &x: a)
		cin >> x;
	for (int i = 0; i <= n; ++i) 
		dp[i][0][0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= s; ++j) {
			dp[i + 1][j][1] = sum_mod(dp[i + 1][j][1], sum_mod(dp[i][j][0], dp[i][j][1]));
			dp[i + 1][j][2] = sum_mod(dp[i + 1][j][2], sum_mod(sum_mod(dp[i][j][0], dp[i][j][1]), dp[i][j][2]));
			if (j + a[i] <= s) {
				dp[i + 1][j + a[i]][1] = sum_mod(dp[i + 1][j + a[i]][1], sum_mod(dp[i][j][0], dp[i][j][1]));
				dp[i + 1][j + a[i]][2] = sum_mod(dp[i + 1][j + a[i]][2], sum_mod(dp[i][j][0], dp[i][j][1]));
			}
		}
	}
	cout << dp[n][s][2] << '\n';
}


Measured memory_bytes: 211328
def examA():
    C = SI()
    ans = chr(ord(C)+1)
    print(ans)
    return

def examB():
    N,K,M = LI()
    A = LI()
    ans = N*M-sum(A)
    if ans>K:
        ans = -1
    elif ans<0:
        ans = 0
    print(ans)
    return

def examC():
    N, M = LI()
    ansT = 0; ansP = 0
    d = defaultdict(bool)
    WA = [0]*(N+1)
    for i in range(M):
        S, P = LSI()
        S = int(S)
        if P=="WA":
            WA[S] +=1
        elif P=="AC":
            if d[S]:
                continue
            else:
                d[S] = True
                ansT +=1
                ansP +=WA[S]
    print(ansT,ansP)
    return


def bfs_grid(h,w,s,maze):
    distance = [[-1]*w for _ in range(h)]
    def bfsg():
        queue = deque()
        queue.append(s)
        distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.popleft()
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#'):
                    if distance[ny][nx]<=distance[y][x]+1 and distance[ny][nx]!=-1:
                        continue
                    queue.append((ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfsg()
def examD():
    H,W = LI()
    S = [SI() for _ in range(H)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j]=="#":
                continue
            D = bfs_grid(H, W, [i, j], S)
#            print(D)
            cur = 0
            for d in D:
                cur = max(cur,max(d))
            ans = max(ans,cur)
    print(ans)
    return

def examE():
    N, K = LI()
    A = LI()

    return

def examF():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()


Measured memory_bytes: 46936
"""
考察

一点を(0,0におくと)
s / 2 = abs(x1*y2 - x2*y1) / 2
abs(x1*y2 - x2*y1) = s
(x1,y1)になにか入れてみるとして、0を入れると点2のx,yどっちかが消えるので良くない
また、absが邪魔なので、absの一項目を大きくとって、二項目をちいさくとりたい。
ので、10**9 * y2 - x2 = sとする。
s = 10**9 * y2 + x2 ならsを10**9で割った商と余りなのだけども。

s / 10**9 = a あまり bとして、
s / 10**9 = a + 1 あまり +(b-10**9) だから、
y2 = a+1, x2 = 10**9 - b
かな
ただしSが10**9で割り切れるときは x2 = 0
"""

S = int(input())
x0,y0,x1,y1 = 0,0,10**9,1

if S % 10**9 == 0:
    x2, y2 = 0, S // 10**9
else:
    x2, y2 = 10**9 - (S % 10**9), S // 10**9 + 1

print(x0,y0,x1,y1,x2,y2)

Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 998244353;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll c(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
ll dp[3001][3001];
int main(void) {
	rep(i, 0, 5) {
		int a;
		cin >> a;
		if (a == 0)printf("%d\n", i + 1);
	}
	return 0;
}


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

int main(){
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  
  int sml = min(A,C);
  string ans;
  
  while(sml > 0){
    C = C - B;
    sml = min(A,C);
    if(sml <= 0){
      ans = "Yes";
      break;
    }
    
    A = A - D;
    sml = min(A,C);
    if(sml <= 0){
      ans = "No";
      break;
    }
  }
  
  cout << ans << endl;
    
  
}

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

S = [input() for _ in range(N)]

AC = 0
WA = 0
TLE = 0
RE = 0

for s in S:
    if s == "AC":
        AC += 1
    elif s == "WA":
        WA += 1
    elif s == "TLE":
        TLE += 1
    else:
        RE += 1
        
print('AC x', AC)
print("WA x", WA)
print('TLE x', TLE)
print('RE x', RE)

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

#define F first
#define S second
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(int i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7;
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class T> void dbs(string str, T t) {cout << str << " : " << t << endl;}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cout << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void prc(T a, T b) {cout << "["; for (T i = a; i != b; ++i) {if (i != a) cout << ", "; cout << *i;} cout << "]";cout<<endl;}

const int N = 1e3 + 10;
vector<int> g[N];
int a[N];

int check(const vector<ii>& x, int val) {
	bitset<5010> b;
	b[0] = 1;
	for (auto it: x) {
		b = (b << it.F) | (b << it.S);
	}
	NFOR (i, val, 0) if (b[i]) return i;
	return inf;
}

ii f(int x) {
	vector<ii> yo;
	int sum = 0;
	for (int y : g[x]) {
		auto z = f(y);
		if (z.F == -1) return z;
		sum += z.F + z.S;
		yo.push_back(z);
	}
	int val = check(yo, a[x]);
	if (val <= a[x])
		return ii(a[x], sum - val);
	return ii(-1, -1);
}

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

	int n; cin >> n;

	FOR (i, 2, n) {
		int p; cin >> p;
		g[p].push_back(i);
	}

	FOR (i, 1, n) cin >> a[i];

	if (f(1).F == -1) cout << "IM";
	cout << "POSSIBLE\n";

	return 0;
}


Measured memory_bytes: 384
#include<iostream>
int main(){

  int n,a;
  std::cin>>n;

  int Adj[100][100],adj[100][100]={0},find[100][2],back[100][100],depth[100]={0},endflag[100]={0},flag;
	int u[n],k[n],kcou=0,timenow=0,v,pred,prev,firstv,backcount[100]={0},flag1=0;
  for(int i=0;i<n;i++){
    std::cin>>u[i];
    std::cin>>k[i];
    for(int j=0;j<k[i];j++){
      std::cin>>Adj[i][j];
    }
  }
	
	/*
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    	std::cout<<Adj[i][j]<<" ";
    }
  	std::cout<<"\n";
  }*/
	
	v=0;
	firstv=0;
	while(timenow<n*2){
		flag=0;
		if(find[firstv][0]!=NULL&&find[firstv][1]!=NULL){
			for(int i=0;i<n;i++){
				if(find[i][0]==NULL){
					//std::cout<<i<<"\n";
					firstv=i;
					v=i;
					break;
				}
			}
		}
		
		// std::cout<<"v="<<v+1<<" ";
		//std::cout<<find[v][0]<<" "<<find[v][1];
		// std::cout<<" endflag="<<endflag[v]<<" ";
		if(find[v][0]==NULL){
			timenow++;
			find[v][0]=timenow;
			// std::cout<<v+1<<"[0]= '"<<timenow<<"' ";
			flag=1;
			//std::cout<<flag<<" 1";
		}else if(find[v][1]==NULL){
			if(endflag[v]==1){
				if(backcount[v]<=1){
				timenow++;
				find[v][1]=timenow;
				// std::cout<<v+1<<"[1]= '"<<timenow<<"' ";
				}
				flag=2;
			}
			//std::cout<<flag;
		}else{
			backcount[v]--;
			v=back[v][backcount[v]];
			//backcount[v]--;
			flag=3;
			//std::cout<<flag<<" 0";
		}

		if(flag==0){
				pred=depth[v];
				depth[v]++;
				prev=v;
				v=Adj[v][pred]-1;
				back[v][backcount[v]]=prev;
				backcount[v]++;
				//std::cout<<flag<<"\n";
		}else if(flag==1){
			if(endflag[v]==0){
				if(Adj[v][depth[v]]-1!=v){
					while(find[Adj[v][depth[v]]-1][0]!=NULL && k[v]-1!=depth[v]){
						depth[v]++;
					}
					if(find[Adj[v][depth[v]]-1][0]==NULL){
						pred=depth[v];
						depth[v]++;
						prev=v;
						v=Adj[v][pred]-1;
						back[v][backcount[v]]=prev;
						backcount[v]++;
					}else{
						depth[v]++;
					}
				}else{
					pred=depth[v];
					depth[v]++;
				}
			}
		}else if(flag==2){
			backcount[v]--;
			v=back[v][backcount[v]];
			//backcount[v]--;
			//std::cout<<flag<<"\n";
		}
		if(depth[v]>k[v]-1){
			endflag[v]=1;
		}
		// std::cout<<"flag="<<flag<<"\n";
	}
	
	
	
	
  for(int i=0;i<n;i++){
     std::cout<<i+1<<" "<<find[i][0]<<" ";
     std::cout<<find[i][1]<<"\n";
    //std::cout<<"\n";
  }

  return 0;
}


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

#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (ll i = m; i < (n); i++)

using ll = long long;
using pii = pair<int, int>;
using Vi = vector<int>;


int main(){
  ll a,b,c,d;
  cin >> a>>b>>c>>d;
  ll A,B,C,D;
  A = a*c;
  B = a*d;
  C = b*c;
  D = b*d;
  
  cout << max(max(A,B), max(C,D)) << endl;
  
    
}

Measured memory_bytes: 3672
from collections import defaultdict
import heapq

vertices,edges = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
way = [float("inf")] * vertices
for e in range(edges):
    source,target,w = map(int,input().split(" "))
    link[source] = link.get(source,set()) | {target}
    link[target] = link.get(target,set()) | {source}
    weight[source].update({target:w})
    weight[target].update({source:w})
queue = []
heapq.heapify(queue)
heapq.heappush(queue,[0,0])
went = [0] * vertices
now_weight = 0
way[0] = 0

while queue:
    here_weight,here = heapq.heappop(queue)
    #print(went)
    if went[here]:
        continue
    went[here] = 1
    now_weight += here_weight
    min_weight,next_t = float("inf"),-1
    for c in link[here]:
        if not went[c] and way[c] > weight[here][c]:
            heapq.heappush(queue,[weight[here][c],c])
            way[c] = weight[here][c]
    #print(queue)
print(now_weight)

Measured memory_bytes: 43800
/* 実行時間1s制限の場合10^6 1,000,000 : 余裕をもって間に合う10^7
  10,000,000 : おそらく間に合う10^8 100,000,000 : 非常にシンプルな処理
  でないと厳しい
 */
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll; // long longはデータモデル(LLP64, LP64, ...)によらず64bit.
ll gcd(ll a, ll b) {return b ? gcd(b, a%b) : a;}  // Greatest Common Divisor ユークリッドの互除法（aが長辺）
vector<pair<ll,int>> factorize(ll n) {            // a,bの公約数 = GCD(a, b)の約数
    vector<pair<ll,int>> res;
    for (ll i = 2; i*i <= n; i++) { // √nまで探せばよい
        if (n%i) continue;
        res.emplace_back(i, 0);     // 割り切れたら
        while (n%i == 0) {
            n /= i;
            res.back().second++;
        }
    }
    if (n != 1) res.emplace_back(n, 1); // この時点で1でなかったら、残りは素数.
    return res;
}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}         // Least Commont Multiple オーバーフローしないように先に割る
ll ceil(ll a, ll b) {return (a+b-1)/b;}

const ll INF = LONG_MAX;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(int argc, char* argv[])
{
#ifdef LOCAL
    // 以降 cin の入力元が 'xxx.txt' になる
    // std::ifstream in(argv[1]);
    //std::cin.rdbuf(in.rdbuf());
    //std::ifstream in(string(argv[0]) + ".txt");
    std::ifstream in("in.txt");
    std::cin.rdbuf(in.rdbuf());
#endif


    ll n, a, b;
    cin >> n >> a >> b;

    ll ans = 0;

    ll s = n / (a+b);
    ll r = n % (a+b);

    if (a == 0) {
        cout << "0";
    }
    else {
        cout << a*s + min(a, r);
    }



    return 0;
}

/*
  - 1e9 : 10^9
  - container一般
    - 合計
      accumulate(a.begin(), a.end(), 0LL)  0LLはオーバーフロー用
  - vector
    vector<int> A(N, 0); // 0で初期化(省略可)
    - loop
      for  (int i = 0; i < A.size(); i++) {}
      for  (int elem : A) {}
    - sort
      std::sort(v.begin(), v.end());  // 昇順
      std::sort(v.begin(), v.end(), std::greater<int>()); //降順
      - vector<vector<int>> cnt(h, vector<int>(w))
    - sort(struct)
        struct st_t {
            string name;
            int p;
            bool operator<(const st_t& another) const {
                if (name == another.name)
                {
                    return p > another.p;
                }
                return name < another.name;
            }
        };
        vector<st_t> st(n);
        sort(st.begin(), st.end());
  - pair
    - pairのソートの定義 : firstが優先的に比較。同じだったらsecond。
    - pair<pair<string,int>,int> p[110];
      std::sort(p,p+a);
        こうすると、first.first -> first.second -> secondの順にソートされる
    - sort
      - sort(a.begin(), cb.end(), greater<pair<int, int>>());
  - map
    - for (auto x : map) {}  // x.first:key  x.second:value.
  - priority_queue<int> q;
    - q.top()に最大値が入っている
  - string
    - loop
      for (char& c : s) {}
 */



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

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<pair<int, int>, int> PP;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
//------------------------------------------------------------------------------------------------------------------------------

int main(void) { 
    int N;
    cin >> N;
    string S;
    cin >> S;
    int ans = 0;
    for (int i = 0; i < N;) {
        int j = i;
        while(j < N){
            if (S[j] != S[i]) break;
            j++;
        }
        ans++;
        i = j;
    }
    cout << ans << endl;
}


Measured memory_bytes: 512
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K, L = MAP()
pq = [LIST() for _ in range(K)]
rs = [LIST() for _ in range(L)]

class UnionFind:
   def __init__(self, n):
       self.par = [i for i in range(n+1)]
       self.rank = [0] * (n+1)
   # 検索
   def find(self, x):
       if self.par[x] == x:
           return x
       else:
           self.par[x] = self.find(self.par[x])
           return self.par[x]
   # 併合
   def union(self, x, y):
       x = self.find(x)
       y = self.find(y)
       if self.rank[x] < self.rank[y]:
           self.par[x] = y
       else:
           self.par[y] = x
           if self.rank[x] == self.rank[y]:
               self.rank[x] += 1
   # 同じ集合に属するか判定
   def same_check(self, x, y):
       return self.find(x) == self.find(y)

tree_road = UnionFind(N)
tree_train = UnionFind(N)
for p, q in pq:
	tree_road.union(p, q)

for r, s in rs:
	tree_train.union(r, s)

dic = defaultdict(int)
for i in range(1, N+1):
	dic["({},{})".format(tree_road.find(i), tree_train.find(i))] += 1

for i in range(1, N+1):
	print(dic["({},{})".format(tree_road.find(i), tree_train.find(i))], end=" ")


Measured memory_bytes: 97412
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define de(x) cout << #x << "=" << x << endl;
template <class T>
bool maxi(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool mini(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
using namespace std;
using ll = long long;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------

//--MAIN-----------------------------------
void Main() {
    ll N; cin>>N;
    vector<ll> A(N);
    rep(i,N) cin>>A[i];
    ll ans=0;

    rep(i,61){
        ll su0=0;
        ll su1=0;
        rep(j,N){
            if((A[j]>>i) & 1) ++su1;
            else ++su0;
        }
        ans+=((su1*su0)%MOD)*((1LL <<i)%MOD);
        ans%=MOD;
    }

    cout<< ans<<"\n";

}

//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 2560
package main

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

func main() {
	sc := NewScanner()
	N := sc.NextInt()
	A := sc.NextIntArray()

	total := 0
	for i := 0; i < N; i++ {
		total += A[i]
	}

	fmt.Println(total - N)
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}
func (s *Scanner) NextInt64Array() []int64 {
	s.pre()
	start := s.p
	result := []int64{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)
			result = append(result, v)
			start = s.p + 1
		}
	}
	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

const int MAX = 5e5;

long long fac[MAX], finv[MAX], inv[MAX];

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

// 二項係数計算
long long COM(ll n, ll k){
  if(n >= MAX){
    ll tmp = 1;
    rep(i,k){
      tmp *= (n-i);
      tmp %= MOD;
    }
    return tmp*finv[k]%MOD;
  }

  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll POW(ll x, ll n){
  ll ret = 1;
  while(0 < n){
    if(n%2 == 0){
      x = x*x%MOD;
      n = n >> 1;
    }
    else{
      ret = ret*x%MOD;
      n--;
    }
  }
  return ret;
}

int main(){
  int n; cin >> n;
  int num[10][10] = {0};
  for(int i = 1; i < n+1; i++) {
    int n1 = i%10;
    string s = to_string(i);
    int n2 = s[0] - '0';
    num[n1][n2]++;
  }
  ll ans = 0;
  for(int i = 1; i < 10; i++) {
    for(int j = 1; j < 10; j++) {
      ans += num[i][j]*num[j][i];
    }

  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define F first
#define S second
#define endl '\n'
#define lcm( a, b ) ((a)/__gcd(a,b)*(b))
#define MP make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<int, P> i_P;
typedef pair< LL, LL > L_P;

const int INF = INT_MAX;
const int MIN = INT_MIN;
const LL LINF = LLONG_MAX;
const int MOD = 1000000000 + 7;
const int SIZE = 100005;

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

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

        for( int k = 0; k < n; ++k ) {
            int res[4][4];
            int in[8];
            for( int i = 0; i < 8; ++i ) {
                cin >> in[i];

            }
            for( int i = 0; i < 4; ++i ) {
                for( int j = 0; j < 4; ++j ) {
                    res[i][j] = in[i] * in[4 + j];

                }
            }
            res[0][0] += res[1][1] * -1 + res[2][2] * -1 + res[3][3] * -1;
            res[0][1] += res[1][0] + res[2][3] + -res[3][2];
            res[0][2] += -res[1][3] + res[2][0] + res[3][1];
            res[0][3] += res[1][2] + -res[2][1] + res[3][0];
            cout << res[0][0] << " " << res[0][1] << " " << res[0][2] << " " << res[0][3] << endl;

        }
    }

    return 0;
}




Measured memory_bytes: 3188
from collections import deque

def main():
    K = int(input())

    q = deque()
    for i in range(1, 10):
        q.append(i)

    count = 0
    while (True):
        x = q.popleft()
        if x % 10 != 0:
            q.append(10*x+(x%10)-1)
        q.append(10*x+(x%10))
        if x % 10 != 9:
            q.append(10*x+(x%10)+1)
        if count == K-1:
            print(x)
            break
        count += 1

if __name__ == '__main__':
    main()

Measured memory_bytes: 11888
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <numeric>
#include <cmath>

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

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

const ll MOD = 1000000007;
const int INF = 1<<30;
//const ll INF = (ll)1e18 + 1;

int main(){
  ll A, B, C; cin >> A >> B >> C;
  if (A == B && B == C && C == A && A % 2 == 0) cout << -1 << endl;
  else if (A == B && B == C && C == A && A % 2 != 0) cout << 0 << endl;
  else {
    ll ans = 0;
    while (A % 2 == 0 && B % 2 == 0 && C % 2 == 0){
      ll tmp1 = A, tmp2 = B, tmp3 = C;
      A = (tmp2 + tmp3) / 2;
      B = (tmp1 + tmp3) / 2;
      C = (tmp1 + tmp2) / 2;
      ++ans;
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 256
n = gets.to_i
a_array=gets.chomp.split(" ").map(&:to_i)
b_array=gets.chomp.split(" ").map(&:to_i)
c_array=gets.chomp.split(" ").map(&:to_i)

ret = 0
(0...n).each do |i|
    r = a_array[i] - 1
    ret += b_array[r]
    if i > 0 && a_array[i] == a_array[i-1] + 1
        ret += c_array[r-1]
    end
end

puts ret

Measured memory_bytes: 1788
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		long monster_kensu = sc.nextLong();
		long kill_kaisu = sc.nextLong();

		if (monster_kensu <= kill_kaisu) {
			System.out.println("0");
		} else {
			List<Long> monster_list = new ArrayList<>();

			for (int i = 0; i < monster_kensu; i++) {
				monster_list.add(sc.nextLong());
			}

			Collections.sort(monster_list, Collections.reverseOrder());
          long attack_sum = 0;
				attack_sum = monster_list.stream().mapToLong(Long::longValue).skip(kill_kaisu).sum();
          System.out.println(attack_sum);
		}
	}
}

Measured memory_bytes: 85192
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

long long n;
char s[105],t[105];

int main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

cin >> n;

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


return 0;
}



Measured memory_bytes: 256
#include<iostream>

using namespace std;

class Dice{
  private:
    int d_1,d_2,d_3,d_4,d_5,d_6;
  public:
    void setDice(int a,int b,int c,int d,int e,int f){
      d_1 = a;
      d_2 = b;
      d_3 = c;
      d_4 = d;
      d_5 = e;
      d_6 = f;
    }
    void roll_w(){
      int tmp = d_1;
      d_1 = d_3;
      d_3 = d_6;
      d_6 = d_4;
      d_4 = tmp;
    }
    void roll_e(){
      int tmp = d_1;
      d_1 = d_4;
      d_4 = d_6;
      d_6 = d_3;
      d_3 = tmp;
    }
    void roll_n(){
      int tmp = d_1;
      d_1 = d_2;
      d_2 = d_6;
      d_6 = d_5;
      d_5 = tmp;
    }
    void roll_s(){
      int tmp = d_5;
      d_5 = d_6;
      d_6 = d_2;
      d_2 = d_1;
      d_1 = tmp;
    }

    void spin(){
      int tmp = d_2;
      d_2 = d_3;
      d_3 = d_5;
      d_5 = d_4;
      d_4 = tmp;
    }

    int findRight(int top,int front){
      for(int i=0;i < 6;i++){
        for(int j=0;j < 4;j++){
          if((*this).d_1 == top && (*this).d_2 == front) return (*this).d_3;
          (*this).spin();
        }
        if(i % 2 == 0)
        (*this).roll_n();
        else
        (*this).roll_w();
      }
      return -1;
    }

    bool cmpDice(Dice d2){
      for(int i=0;i < 6;i++){
        for(int j=0;j < 4;j++){
          if((*this).d_1 == d2.d_1 && (*this).d_2 == d2.d_2 && (*this).d_3 == d2.d_3
          && (*this).d_4 == d2.d_4 && (*this).d_5 == d2.d_5 && (*this).d_6 == d2.d_6){
            return true;
          }
          d2.spin();
        }
        if(i % 2 == 0) d2.roll_n();
        else d2.roll_w();
      }
      return false;
    }

    int getDice(){
      return d_1;
    }

};

int main(){
  int n;
  int a,b,c,d,e,f;
  bool ok = true;
  Dice D[100];
  cin >> n;
  for(int i=0;i < n;i++){
    cin >> a >> b >> c >> d >> e >> f;
    D[i].setDice(a,b,c,d,e,f);
  }
  for(int i=0;i < n;i++){
    for(int j=0;j < n;j++){
      if(i==j) continue;
      if(D[i].cmpDice(D[j])){
        ok = false;
        break;
      }
    }
    if(!ok) break;
  }
  if(ok) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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

int main()
{
    string s;
    cin >> s;
    int zero = 0, one = 0;

    for (auto &c : s)
    {
        if (c == '0')
        {
            zero++;
        }
        else
        {
            one++;
        }
    }

    cout << 2 * min(zero, one) << endl;
}

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

//3重ループだと間に合わない

int main(){
  int n ;
  cin >> n;
  long long y;
  cin >> y;
  int a =-1; int b=-1; int c=-1;
  
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n-i;j++){
      int k = n-i-j;
      if(10000*i+5000*j+1000*k==y){
       a = i; b=j; c=k;
        break;
      }
    }
  }
   cout << a << ' ' << b << ' ' << c <<endl;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(a)      (a).begin(),(a).end()
#define debug_array(a,n) for (ll bccc=(0); bccc<(n); bccc++) cout<<a[bccc]<<" "<<"\n"
#define debug_vector(a) for(ll bccc=(0); bccc<(a.size());bccc++) cout<<a[bccc]<<" "<<"\n"
#define F           first
#define S           second
#define debug_set(s) for(auto p:s) cout<<p<<" "
#define debug_map(m) for(auto p:m) cout<<p.F<<" "<<p.S<<"\n"
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<pair<ll,ll>,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;

/* ll t = 0;
ordered_multiset me;
...
me.insert({x, t++});
me.erase(me.lower_bound({x, 0}));
cout << me.order_of_key({x, 0}) << "\n";

///////////   t is insertion time
*/
//#pragma GCC optimize("Ofast")  // works very well
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef long double lld;
lld pi=3.14159265358;
ll powr(ll a,ll b)
{
    ll c=1;
    ll kjk;
    for(kjk=0;kjk<b;kjk++)
        c*=a;
    return c;
}
ll hell=1000000007;
//ll hell=998244353   ;
ll power(ll x, ll y, ll p)
{
    ll res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
// to generate random number , use rng() ... eg cout<<rng();
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll a;
    cin>>a;
    cout<<a + a*a + a*a*a;

    return 0;
}


Measured memory_bytes: 3640
S = input()
K = int(input())
flag = True
num = 0
ans = ''
for k in range(len(S)):
    if flag and S[k] == '1':
        num += 1
    else:
        flag = False
    if S[k] != '1':
        ans = S[k]
        break
if num >= K:
    print(1)
else:
    print(ans)


Measured memory_bytes: 3060
n = int(input())
alst = [int(input()) for i in range(n)]

flag = 0
ans = 0
temp = -1
ind = 0
while ind < n:
  a = alst[ind]
  if a - temp > 1:
    flag = 1
    break
  while ind + 1 < n and alst[ind + 1] == a + 1:
    ind += 1
    a = alst[ind]
  ans += a
  temp = a
  ind += 1

if not flag:
  print(ans)
else:
  print(-1)


Measured memory_bytes: 11048
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);

		int N = scan.nextInt();

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


Measured memory_bytes: 21844
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
using namespace std;

/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long ll;

#define fi first
#define se second

using Graph = vector<vector<int>>;

int main()
{
    ll a, b, c, k;
    cin >> a >> b >> c >> k;

    if (a >= k)
    {
        cout << k << endl;
    }
    else if (a + b >= k)
    {
        cout << a << endl;
    }
    else
    {
        cout << a - (k - a - b) << endl;
    }

    return 0;
}

Measured memory_bytes: 3632
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=5;
int state[50][50];
char fld[50][51];
int h,w;
const int dx[]={0,-1,0,1};
const int dy[]={-1,0,1,0};
void dfs(int y,int x,int clr){
    if(y<0||y>=h||x<0||x>=w)return;
    if(state[y][x]==INF)return;
    if(fld[y][x]!='.')return;
    if(state[y][x]==clr)return;
    if(-state[y][x]==clr)state[y][x]=INF;
    else state[y][x]=clr;
    for(int i=0;i<4;i++)dfs(y+dy[i],x+dx[i],clr);
}
void debug(){
    puts("---debug---");
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++)printf("%2d ",state[i][j]);
        puts("");
    }
}
int main(){
    while(scanf("%d%d",&w,&h),w||h){
        for(int i=0;i<h;i++)scanf("%s",fld[i]);
        fill_n(*state,50*50,0);
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(fld[i][j]=='.')continue;
                int clr=(fld[i][j]=='B'?1:-1);
                for(int k=0;k<4;k++)dfs(i+dy[k],j+dx[k],clr);
            }
        }
        //debug();
        int B=0,W=0;
        for(int i=0;i<h;i++){
            B+=count(state[i],state[i]+w,1);
            W+=count(state[i],state[i]+w,-1);
        }
        printf("%d %d\n",B,W);
    }

    return 0;
}

Measured memory_bytes: 1096
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    
    vector<int> c(9);
    for(int i=0;i<9;i++){
        cin >>c[i];
    }
    if((c[0]-c[3]==c[1]-c[4])&&(c[2]-c[5]==c[1]-c[4])&&(c[0]-c[6]==c[1]-c[7])&&(c[2]-c[8]==c[1]-c[7])&&(c[0]-c[1]==c[3]-c[4])&&(c[6]-c[7]==c[3]-c[4])&&(c[0]-c[2]==c[3]-c[5])&&(c[6]-c[8]==c[3]-c[5])) {
        cout <<"Yes";
    }else{
        cout <<"No";
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll N, M; cin >> N >> M;
  priority_queue<
    ll,
    vector<ll>,
    greater<ll>
  > A; 
  for(ll i=1; i<=N; i++){
    ll temp;
    cin >> temp;
    A.push(temp);
  }
  
  vector<vector<ll>> v;
  ll B,C;
  for(ll i=1; i<=M; i++){
    cin >> B >> C;
    v.push_back({C, B});
  }
  sort(v.begin(), v.end(),greater<vector<ll>>());
  
  for(ll i=1; i<=M; i++){
    ll count=0;
    B=v[i-1][1]; 
    C=v[i-1][0];
//    cout << B << ' ' << C << endl;
    while(A.top()<C && count < B) {
      A.pop();
      A.push(C);
      count++;
    }
  }
  
  ll dest=0;
  for(ll i=1; i<=N; i++){
//    cout << A.top() << endl;
    dest+= A.top();
    A.pop();
  }
  cout << dest;



}


Measured memory_bytes: 7408
#include <iostream>

using namespace std;

const int N = 1e5 + 7;

int v[N], d[N];

int abs(int val) {
    return max(val, -val);
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> v[i];
    d[0] = 0;
    d[1] = abs(v[0] - v[1]);
    for (int i = 2; i < n; ++i)
        d[i] = min(d[i - 1] + abs(v[i] - v[i - 1]), d[i - 2] + abs(v[i] - v[i - 2]));
    cout << d[n - 1];
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int cl(int a, int b) {
	return (a - (a%b)) / b;//b=0だと積む
}
int up(int a, int b) {
	return cl(a + b - 1, b);//b=0だと積む
}
int ord(int a, int p) {
	if (a%p == 0) {
		return ord(a / p, p) + 1;
	}
	else {
		return 0;
	}
}
long long ruin(int a, int n, long long  p) {
	if (n == 0) {
		return (1%p);
	}
	else {
	long long x = ruin(a, (n - (n % 2)) / 2, p);
		if (n % 2 == 0) {
			return (x*x) % p;
		}
		else {
			return (((x*x) % p)*a) % p;
			
		}
	
	}
	
}
long long com(int n, int r, int p) {
	if (r == 0) {
		return (1%p);
	}
	else {
		long long x = com(n, r - 1, p);
		return (x*(n - r) / r) % p;
	}
}
int main() 
{
	int n, m;
	cin >> n >> m;
	vector<int> d(n);
	vector<int> c(m);
	for (int i = 0; i < n; i++) {
		cin >> d[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> c[i];
	}
	vector<int> t(n + 1,1000000003);
	vector<int> yo(n + 1);
	t[0]=0;
	for (int da = 0; da < m; da++) {
		int cl = c[da];
		yo = t;
		for (int i = 0; i < n; i++) {
			t[i + 1] = min(t[i + 1], yo[i] + (d[i] * cl));
		}
	}
	cout << t[n] << endl;
}



Measured memory_bytes: 3176
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <utility>
using namespace std;
#define MAXSIZE 200
#define MAXL 100
typedef long long int lli;

int main(){
    int n;
    cin >> n;
    vector<int> value_vec, cost_vec;
    for(int i = 0; i != n; ++i){
        int value_input;
        cin >> value_input;
        value_vec.push_back(value_input);
    }
    for(int i = 0; i != n; ++i){
        int cost_input;
        cin >> cost_input;
        cost_vec.push_back(cost_input);
    }

    int cur_sub = 0, max_sub = 0;
    int value_sum = 0, cost_sum = 0;
    for(int i = 0; i != n; ++i){
        if((value_sum + value_vec[i]) - (cost_sum + cost_vec[i]) > max_sub){
            value_sum += value_vec[i];
            cost_sum += cost_vec[i];
            max_sub = value_sum - cost_sum;
        }
    }
    
    int ans = max_sub;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
object Main extends App {
	val s = scala.io.StdIn.readLine

	var a = 0 // 01
	var b = 0 // 10
	var c = '0'

	for(i<-0 until s.size){
		if(s(i) == c) b += 1
		else if(s(i) != c) a += 1

		if(c == '0') c = '1'
		else c = '0'
	}


	println(math.min(a, b))
}


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

int main() {

    string S;
    cin>>S;
    bool A=false;
    for(int i=0;i<3;i++){

    if(S.at(i)=='7'){
        A=true;

    }}

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

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

using namespace std;

typedef long long ll;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> b = a;
    ll k1 = 0, k2 = 0;
    ll s = a[0];
    if (!s) {
        ++s;
        ++k1;
    }
    for (int i = 1; i < n; ++i) {
        if (s + a[i] == 0) {
            ++k1;
            if (s > 0) {
                s = -1;
            } else {
                s = 1;
            }
            continue;
        }
        if ((s > 0) ^ (s + a[i] < 0)) {
            k1 += abs(s + a[i]) + 1;
            if (s > 0) {
                s = -1;
            } else {
                s = 1;
            }
        } else {
            s += a[i];
        }
    }
    if (a[0] == 0) {
        s = -1;
        ++k2;
    } else {
        if (a[0] > 0) {
            s = -1;
            k2 += a[0] + 1;
        } else {
            s = 1;
            k2 -= a[0] - 1;
        }
    }
    for (int i = 1; i < n; ++i) {
        if (s + a[i] == 0) {
            ++k2;
            if (s > 0) {
                s = -1;
            } else {
                s = 1;
            }
            continue;
        }
        if ((s > 0) ^ (s + a[i] < 0)) {
            k2 += abs(s + a[i]) + 1;
            if (s > 0) {
                s = -1;
            } else {
                s = 1;
            }
        } else {
            s += a[i];
        }
    }
    cout << min(k1, k2);
    return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
int main(){

int a,max1=0,max2=0,max3=0,i;
for(i=0;i<10;i++){
	scanf("%d",&a);
	if(max1<a){
		max3=max2;
		max2=max1;
		max1=a;
	}
	else if(max2<a){
		max3=max2;
		max2=a;
	}
	else if(max3<a)
	max3=a;
	}
	printf("%d\n%d\n%d\n",max1,max2,max3);
return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    ll n;
    cin >> n;
    int mx = 10000001;
    vector<ll> cnt(mx, 2);
    cnt[1]--;
    rep(i, 2, 6000000) {
        int s = i * 2;
        for (int j = s; j <= mx; j += i) {
            cnt[j]++;
        }
    }
    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        ans += i * cnt[i];
    }
    cout << ans << endl;
    return 0;
}


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

int check( string s, int pos )
{
    int len = 0;

    for( ; pos < s.length() ; pos++ )
    {
        if( s[pos] == 'A' || s[pos] == 'T' || s[pos] == 'C' || s[pos] == 'G' ) len++;
        else break;
    }
  
    return len;
}

int main() 
{
    string S;
    cin >> S;
    int len = 0;

    for( int i=0 ; i<S.length() ; i++ )
    {
        int a = check( S, i );
        if( a > len ) len = a;
    }

    cout << len << endl;
}

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

using namespace std;

int main()
{
  int n;
  cin>>n;
  int ac,wa,tle,re;
  ac=wa=tle=re=0;

  for(int i=0;i<n;i++)
  {
      string s;
      cin>>s;
      if(s=="AC") ac++;
      else if(s=="WA") wa++;
      else if(s=="TLE") tle++;
      else if(s=="RE") re++;
  }

  cout<<"AC x "<<ac<<endl;
  cout<<"WA x "<<wa<<endl;
  cout<<"TLE x "<<tle<<endl;
  cout<<"RE x "<<re<<endl;

    return 0;
}


Measured memory_bytes: 3632
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N,L[2001],Lnum[2001]={},Lnumsum[2001]={};
	scan(N);
	rep(i,N){
		scan(L[i]);
		Lnum[L[i]]++;
	}
	rep1(i,2000){
		Lnumsum[i]=Lnumsum[i-1]+Lnum[i];
	}
	ll ans=0;
	rep(i,N){
		for(int j=i+1;j<N;j++){
			int cnum=Lnumsum[L[i]+L[j]-1]-Lnumsum[abs(L[i]-L[j])];
			//printf("L[i]:%d L[j]:%d (%d,%d]:%d\n",L[i],L[j],abs(L[i]-L[j]),L[i]+L[j]-1,cnum);
			if(abs(L[i]-L[j])<L[i]) cnum--;
			if(abs(L[i]-L[j])<L[j]) cnum--;
			ans+=cnum;
		}
	}
	prin(ans/3);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long c[200001];
int h[200001];
long long maxn;
int lowbit(int x)
{
	return x&-x;
}
void increase(int index,long long value)
{
	while(index<=200001)
	{
		c[index]=max(c[index],value);
		index+=lowbit(index);
	}
}
long long maxrange(int index)
{
	long long ret=0;
	while(index)
	{
		ret=max(ret,c[index]);
		index-=lowbit(index);
	}
	return ret;
}
int main()
{
	int n,i;
	long long a,t;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&h[i]);
	}
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a);
		t=maxrange(h[i])+a;
		increase(h[i],t);
		maxn=max(maxn,t);
	}
	printf("%lld",maxn);
	return 0;
}

Measured memory_bytes: 2560