akhauriyash/Code-Regression huggingface dataset:
#https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))

Sum_Weight = sum(map(lambda x:x[0],Goods_List))
dp = [[-1] * (W + 1) for i in range(N)]

for i in range(N):
    Current_Weight = Goods_List[i][0]
    Current_Value  = Goods_List[i][1]
    dp[i][0] = 0
    if (i == 0) & (Current_Weight <= W) :
        dp[i][Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = [j for j, x in enumerate(dp[i-1]) if x > -1]
        Current_Search_List = list(map(lambda x:x+Current_Weight,Last_Search_List))
        ##まずは前回値を入れる
        for l in range(len(Last_Search_List)):
            Last_Search_Weight =  Last_Search_List[l] 
            dp[i][Last_Search_Weight] = dp[i-1][Last_Search_Weight]
        ##今回値と比べる
        for k in range(len(Current_Search_List)):
            Last_Search_Weight =  Last_Search_List[k] 
            Current_Search_Weight = Current_Search_List[k]
            if Current_Search_Weight > W:
                break
            else:
                dp[i][Current_Search_Weight] = max((dp[i-1][Last_Search_Weight] + Current_Value),
                                                   dp[i-1][Current_Search_Weight])


print(max(dp[N-1]))

Measured memory_bytes: 224144
#include<bits/stdc++.h>
using namespace std;
vector<long long>h;
long long mem[100001];
long long n;
long long dp(long long i)
{
    if(i==n-1)
        return 0;
    if(i>n-1)
        return 10000000;
    if(mem[i]!=-1)
        return mem[i];
    mem[i]=min(abs(h[i+1]-h[i])+dp(i+1),abs(h[i+2]-h[i])+dp(i+2));
    return mem[i];
}
int main()
{
    memset(mem,-1,sizeof(mem));
    long long i;
    cin>>n;
    h.resize(n);
    for(i=0;i<n;i++)
        cin>>h[i];
    cout<<dp(0)<<endl;
    return 0;
}


Measured memory_bytes: 4096
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
#define all(n) begin(n), end(n)
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
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 <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}

int M (int a,int b)
{
    return max(a,b);
}
int e(){
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    vint A(N);

    const int MAX = 300100;
    atcoder::segtree<int,M,e> seg(MAX);
    for (size_t i = 0; i < N; i++)
    {
        cin >> A[i];
        A[i];
    }

    for (size_t i = 0; i < N; i++)
    {
        int val = seg.prod(max(0, A[i] - K), min(A[i] + K, MAX - 1)+1);
        seg.set(A[i], 1 + val);
        //cout << "Range : " << (max(0, A[i] - K)) << "," << min(A[i] + K, MAX - 1) << "  " << val << "  ";
        for (size_t j = 0; j < 11; j++)
        {
            //cout << seg.get(j) << " ";
        }
        //cout << endl;
    }
    cout << seg.prod(0, MAX - 1) << endl;

    return 0;
}

Measured memory_bytes: 9896
#include<stdio.h>

#define N 100

int main()
{
  int G[N][N];
  int n,u,k,v;
  int i,j;

  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      for(j=0;j<n;j++)
	{
	  G[i][j]=0;
	}
    }

  
  for(i=0;i<n;i++)
    {
      scanf("%d %d",&u,&k);
      u--;
      for(j=0;j<k;j++)
	{
	  scanf("%d",&v);
	  v--;
	  G[u][v]=1;
	}
    }
   

  for(i=0;i<n;i++)
    {
      for(j=0;j<n;j++)
	{
	  if(j)printf(" ");
	  printf("%d",G[i][j]);
	}
      printf("\n");
    }
  

  return 0;
}



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

using namespace std;

const int nax = 100100;
char plays[nax];
int r,s,p;

void maxi(int &a, int b) {
	a = max(a,b);
}

int get_opt(char c) {
	int total=0;
	if (c == 'r') {
		total += p;
	}	else if (c == 's') {
		total += r;
	} else {
		total += s;
	}
	return total;
}

int main() {
	int n, k;
	cin >> n >> k;
	cin >> r >> s >> p;
	cin >> plays;
	int total=0;
	for (int i=0; i< k; i++) {
		int j = i;
		char last = 'z';
		while (j < n) {
			char v = plays[j];
			if (v != last) {
				total += get_opt(v);
				last = v;
			} else {
				last = 'z';	
			}
			j+=k;
		}	
	}
	cout << total << "\n";
}



Measured memory_bytes: 384
#include <iostream>
#include <string>
#include<algorithm>
#include <cstdlib>
#include <cmath>
#include <regex>

using namespace std;
int main()
{
	int a, b, c, d,ans,m1,m2;
	cin >> a >> b >> c >> d;
	if (a < c) m1 = c;
	else m1 = a;
	if (b > d) m2 = d;
	else m2 = b;
	if (m2 - m1 < 0) ans = 0;
	else ans = m2 - m1;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
d = {}
for a in A:
    d[a - 1] = d.setdefault(a - 1, 0) + 1
    d[a] = d.setdefault(a, 0) + 1
    d[a + 1] = d.setdefault(a + 1, 0) + 1

print(max(d.values()))


Measured memory_bytes: 18752
from math import sqrt
from collections import deque


def divide_repeat(p):
    global n, a, limit
    while not (n % p):
        a.append(p)
        n = n // p
        limit = sqrt(n)


nstr = input()
n, p = int(nstr), 3
limit = sqrt(n)
a, i = deque(), 3

divide_repeat(2)

while p <= limit:
    divide_repeat(p)
    p += 2

if n > 1:
    a.append(n)

print(nstr + ': ', end='')
print(*a)

Measured memory_bytes: 8128
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = 0
t = []
ans = 0
for i in range(n):
    if a[i] < b[i]:
        c += b[i] - a[i]
        ans += 1
    else:
        t.append(a[i]-b[i])
t.sort(reverse=True)
i = 0
while c > 0 and i < len(t):
    ans += 1
    c -= t[i]
    i += 1
if c > 0:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 24288
////////////////////////////////////////////
///                                      ///
///        Template ver. 1.2. rapel      ///
/// Fear is Temporary, Regret is Forever ///
///          Must Try and Get AC         ///
///                                      ///
////////////////////////////////////////////
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <utility>

#include <math.h>
#include <complex>

#include <assert.h>
#include <time.h>
#include <chrono>
#include <random>

#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <list>
#include <bitset>

#define F first
#define S second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define endl '\n'
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void desperate_optimization(int precision){
  	ios_base::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	cout.setf(ios::fixed);
  	cout.setf(ios::showpoint);
  	cout.precision(precision);
}

void hora(int tc) {
	string s;
	cin>>s;
	for(int i = 0;i < 3;i++) cout<<s[i];
	cout<<endl;
}

int main(){
	desperate_optimization(10);
	int ntc = 1;
	//cin>>ntc;
	for(int tc = 1;tc <= ntc;tc++) hora(tc);
	return 0;
}


Measured memory_bytes: 3668
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

max_a = max(a for a, _ in ab)
dp = [0] * (h+max_a)

for i in range(0, h+max_a):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i-a] + b for a,b in ab) 

print(min(dp[h:]))


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

int main() {
    int N; cin >> N;
    vector<double> x(N);
    vector<string> u(N);
    for (int i = 0; i < N; i++) {
        cin >> x.at(i) >> u.at(i);
    }
    double ans = 0;
    
    for (int i = 0; i < N; i++) {
        if (u.at(i) == "JPY") {
            ans += x.at(i);
        }
        else {
            ans += 380000.0 * x.at(i);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#include<queue>
#define ll long long
#define itn int
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
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; }
using namespace std;


int main(){
  double N,K;
  cin>>N>>K;
  vector<double> P,Q;
  P.push_back(0);
  Q.push_back(0);
  
  REP(i,N){
    double a;
    cin>>a;
    P.push_back(a);
  }
  
  double sum=0;
  for(int i=1; i<=N; ++i){
    sum+=P.at(i)+1;
    Q.push_back(sum);
  }
  
  double ans=0;
  
  for(int i=K; i<=N; ++i){
    ans=max(ans,Q.at(i)-Q.at(i-K));
  }
  
  double ANS=ans/2;
  
  cout<<setprecision(10)<<ANS<<endl;
}

Measured memory_bytes: 4848
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int C = sc.nextInt();
    for (int i = 1; i <= B; i++) {
      if ((i * A) % B == C) {
        System.out.println("YES");
        return;
      }
    }
    System.out.println("NO");
  }
}

Measured memory_bytes: 22996
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long N = sc.nextLong();
    long answer =0;
    if(N%2==1){
      System.out.println(0);
      return;
    }
    long tmp = N/2;
    for(long i=1;i<30;i++){
      answer = answer + (long)tmp/(long)(Math.pow((long)5,i));
    }
    System.out.println(answer);
    
    
  }
  

  
}

Measured memory_bytes: 21716
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

const int mx = 10000;
const int sz = 500;
vector<bool> isprime(mx+1, true); 
vll prime;
ll ans[sz][sz];
int di[] = {0, 1, 0, -1};
int dj[] = {-1, 0, 1, 0};

void Eratosthenes(int n){
    isprime[0] = false;
    isprime[1] = false;
    for(int i = 2; i * i <= n; i++){
        for(int j = 2 * i; j <= n; j += i){
            isprime[j] = false;
        }
    }
}

void Solve(){
    rep(i, sz){
        rep(j, sz){
            if((i + j) % 2 == 0) continue;
            int wa = j + i; // 1, 3, 5, 7, 9, ..., 999
            int sa = j - i; // -499, -497, ..., 497, 499
            ans[i][j] = prime[wa/2] * prime[(sa+sz)/2 + sz];
        }
    }
    rep(i, sz){
        rep(j, sz){
            if((i + j) % 2) continue;
            ans[i][j] = 1;
            int wa1 = j + i + 1;
            int wa2 = j + i - 1;
            int sa1 = j - i + 1;
            int sa2 = j - i - 1;
            if(0 < wa1 || wa1 < 2 * sz){
                ans[i][j] *= prime[wa1/2];
            } 
            if(0 < wa2 || wa2 < 2 * sz){
                ans[i][j] *= prime[wa2/2];
            } 
            if(-sz < sa1 || sa1 < sz){
                ans[i][j] *= prime[(sa1+sz)/2 + sz];                
            }
            if(-sz < sa2 || sa2 < sz){
                ans[i][j] *= prime[(sa2+sz)/2 + sz];
            }
            ans[i][j]++;
        }        
    }
}

void Main(){
    Eratosthenes(mx);
    rep(i, mx) if(isprime[i]) prime.pb(i);
    Solve();
    int n; cin >> n;
    rep(i, n) {
        rep(j, n) cout << ans[i][j] << " ";
        cout << endl;
    }
    return;
}

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

Measured memory_bytes: 5604
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;

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

    ll cnt = 0;
    while(b <= a) {
        b *= 2;
        cnt++;
    }
    while(c <= b) {
        c *= 2;
        cnt++;
    }

    if(cnt <= k) {
        out("Yes");
    }
    else {
        out("No");
    }
    
    re0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long u_ll;
typedef pair<int, int> pair_;
 
const int INF = 1001001001;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int k;
 
int gcd(int a, int b){
    if(b == 0) return a;
 
    return gcd(b, a%b);
}
 
int main(){

    int r;

    cin >> r;

    cout << r*r;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>

#include<vector>
#include<string>

#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const ll INF = 1e12+1;
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 N;
    cin >> N;
    vector<ll> x(10000,0);
    vector<bool> prime(10000,true);

    for (int i = 2; i <= N; i++) {
        if (prime[i]) {
            for (int j = 2 * i; j <= N; j += i) {
                prime[j] = false;
            }
            int tmp = i;
            while (tmp <= N) {
                x[i] += (ll) N / tmp;
                tmp *= i;
            }
        }
    }
    ll res = 1;
    ll D = 1e9+7;
    
    for (int i = 2; i <= N; i++) {
        if (prime[i]) res = (res * (x[i]+1)) % D;
    }
    cout << res << endl;

}


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

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

    int64_t ans = 20;
    for (int i = 1; i <= sqrt(n)+1; i++) {
        if (n % i == 0) ans = min(ans, (int64_t) max(log10(i), log10(n / i)));
    }
    cout << ans + 1 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int a, b, c;
int main() {
	cin >> a >> b >> c;
	if (b - a == c - b) cout << "YES" << endl;
	else cout << "NO" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
template<typename T> T min(T a, T b){
	return a<b?a:b;
}
int main(void){
  int n;
  std::cin >> n;
  std::vector<int> b(n-1);
  for(int i = 0; i < n-1; i++){
  	std::cin >> b[i];
  }
  long sum = b[0]+b[n-2];
  for(int i = 0; i < n-2; i++){
  	sum += min<int>(b[i], b[i+1]);
  }
  std::cout << sum << std::endl;
}

Measured memory_bytes: 256
function main(input) {
    const [n, m, k] = shaping(input[0]);
    const a = shaping(input[1]);
    const b = shaping(input[2]);
    if (a[0] > k && b[0] > k) { return console.log(0); }
    let timeA = [0];
    let timeB = [0];
    let ans = 0;
    let sumTime = 0;
    for (let i = 0; i < n; i++){
        sumTime += a[i];
            if (sumTime == k) {
                timeA.push(sumTime);
                break;
            } else if(sumTime > k){
                break;
            }
        timeA.push(sumTime);
    }
    sumTime = 0;
    for (let i = 0; i < m; i++){
        sumTime += b[i];
        if (sumTime == k) {
            timeB.push(sumTime);
            break;
        } else if (sumTime > k) {
            break;
        }
        timeB.push(sumTime);
    }
    let i = 0;
    let j = timeB.length-1;
    while (i < timeA.length) {
        while (j > -1) {
            if (timeB[j] <= k - timeA[i]) {
                if(ans<i+j){ans = i + j};
                break;
            } else {
                j--;
            }
        }
        i++;
    }
    console.log(ans);
}    
function shaping(arr) { 
    return arr.split(' ').map(Number);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"));


Measured memory_bytes: 63588
#include <bits/stdc++.h>
#define ll long long int
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb emplace_back
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define deb(x) cout << #x << " - " << x << endl;

using namespace std;

int main()
{	IOS;
    int a,b; cin>>a>>b;
    if(a>=13) cout<<b;
    else if(a<13&&a>=6) cout<<b/2;
    else if(a<=5) cout<<"0";
	return 0;
}

Measured memory_bytes: 256
a = []
for i in range(3):
    a.extend(list(map(int,input().split())))
n = int(input())
b = []

cnt=[]
pattern=[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]

for i in range(n):
    b.append(int(input()))
    for j , x in enumerate(a):
        if x == b[i]:
            cnt.append(j)

for q,w,e in pattern:
    if q in cnt and w in cnt and e in cnt:
        print('Yes')
        break
else:
    print('No')

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

long long gcd(long long x, long long y) {
    if(y == 0) return x;
    else return gcd(y, x % y);
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << a * b / gcd(a, b) << '\n';
}

Measured memory_bytes: 256
// AtCode.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <stdint.h>
#include <queue>
#include <bitset>

using namespace std;

int main() {

	int H, N;
	cin >> H >> N;

	int count = 0;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		count += tmp;
	}

	if (H <= count) cout << "Yes" << endl;
	else cout << "No" << endl;

	/*
	int H, A;
	cin >> H >> A;

	int ans = H / A + 1;
	cout << ans << endl;
*/

	return 0;
}



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

int main(){
 int n,m,l;
 cin>>n>>m>>l;
 int a[100][100];
 for(int i=0;i<n;i++)
 for(int j=0;j<m;j++)cin>>a[i][j];
 
 int b[100][100];
 for(int i=0;i<m;i++)
 for(int j=0;j<l;j++)cin>>b[i][j];
 
 long long c[100][100]={};
 for(int i=0;i<n;i++)
 for(int j=0;j<l;j++)
 for(int k=0;k<m;k++)c[i][j]+=a[i][k]*b[k][j];
 for(int i=0;i<n;i++){
 for(int j=0;j<l;j++){
 if(j) cout<<" ";
 cout<<c[i][j];
}
cout<<endl;
}
}


Measured memory_bytes: 3220
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <set>
#include <map>
#include <utility>
#include <string>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>

using namespace std;

class UnionFind
{
public:
	UnionFind(int min, int max)
	  : elems_(max - min + 1)
	  , min_(min)
	{
		for (int i = min; i <= max; i++) {
			Elem& elem = this->elems_[i - min];
			elem.i   = i;
			elem.num = 1;
		}
	}

	int find(int i) {
		int idx = i - this->min_;
		if (this->elems_[idx].i == i) return i;

		int root            = this->find(this->elems_[idx].i);
		this->elems_[idx].i = root; // 簡略化
		return root;
	}

	int size(int i) {
		int root = this->find(i);
		int idx  = root - this->min_;
		return this->elems_[idx].num;
	}

	void merge(int i, int j) {
		int i_root = this->find(i);
		int j_root = this->find(j);
		if (i_root == j_root) return;

		int i_idx = i_root - this->min_;
		int j_idx = j_root - this->min_;

		int i_size = this->elems_[i_idx].num;
		int j_size = this->elems_[j_idx].num;

		if (i_size < j_size) {
			this->elems_[i_idx].i    = j_root;
			this->elems_[j_idx].num += this->elems_[i_idx].num;
		}
		else {
			this->elems_[j_idx].i    = i_root;
			this->elems_[i_idx].num += this->elems_[j_idx].num;

		}
	}

private:
	struct Elem {
		int i;
		int num; // root 以外は無効
	};

	vector<Elem> elems_;
	int          min_;
};

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

	std::vector<int[2]> bridges(m);
	for (int i = 0; i < m; i++) {
		cin >> bridges[i][0] >> bridges[i][1];
	}

	uint64_t relations = (uint64_t) n * ((uint64_t) n - 1) / 2;

	UnionFind uf(1, n);

	std::vector<uint64_t> lacks;
	lacks.push_back(relations);

	for (auto bridge = bridges.rbegin(); bridge != bridges.rend(); bridge++) {
		int a = (*bridge)[0];
		int b = (*bridge)[1];

		int a_root = uf.find(a);
		int b_root = uf.find(b);

		if (a_root == b_root) {
			lacks.push_back(*lacks.rbegin());
			continue;
		}

		uint64_t a_size = uf.size(a_root);
		uint64_t b_size = uf.size(b_root);
		uf.merge(a_root, b_root);

		lacks.push_back(*lacks.rbegin() - a_size * b_size);
	}

	for (auto it = lacks.rbegin() + 1; it != lacks.rend(); it++) {
		cout << *it << endl;
	}

	return 0;
}

Measured memory_bytes: 3828
#include<stdio.h>
int main(){
  int r,c,i,j,k=0,a[100][100],b[100];
  for(i=0;i<100;i++){
    b[i]=0;
  }
  scanf("%d %d",&r,&c);
  for(i=0;i<r;i++){
    for(j=0;j<c;j++){
      scanf("%d",&a[i][j]);
    }
  }
  for(i=0;i<r;i++){
    for(j=0;j<c;j++){
      printf("%d ",a[i][j]);
      k=k+a[i][j];
    }
    printf("%d\n",k);
    k=0;
  }
  for(i=0;i<c;i++){
    for(j=0;j<r;j++){
      b[i]=b[i]+a[j][i];
    }
  }
  for(i=0;i<c;i++){
  printf("%d ",b[i]);
  }
  for(i=0;i<r;i++){
    for(j=0;j<c;j++){
      k=k+a[i][j];
    }
  }
  printf("%d\n",k);
  return 0;
}

Measured memory_bytes: 636
def bisect(seq, target):
  left = -1    # ind. always lt target
  right = len(seq)    # ind. always gt or eq to target
  while right - left > 1:
    mid = (left + right) // 2
    if seq[mid] < target:
      left = mid
    else:
      right = mid
  return right



n, m = map(int, input().split())
L = [[] for _ in range(n + 1)]
pairs = [list(map(int, input().split())) for _ in range(m)]
for p, y in pairs:
  L[p].append(y)

for i in range(1, n + 1):
  L[i].sort()


for p, y in pairs:
  left_id = "{:0>6}".format(p)
  right_id = "{:0>6}".format(bisect(L[p], y) + 1)
  print(left_id + right_id)
  


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

int main(){
  int N,a[110];
  int Alice=0,Bob=0;
  cin>>N;
  for(int i=0;i<N;i++)
    cin>>a[i];
  sort(a,a+N,greater<int>());
  for(int i=0;i<N;i++)
  {
    if(i%2==0)
      Alice+=a[i];
    else
      Bob+=a[i];
  }
  cout<<Alice-Bob<<endl;
}

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

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define swap(a, b, type) { type _tmp = a; a = b; b = _tmp; }
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	int H, W;
	string ain, del;
	vector<string> a;
	string::iterator sit;
	vector<string>::iterator it;
	bool flag;

	cin >> H >> W;
	rep(i, H) {
		cin >> ain;
		a.push_back(ain);
	}

	rep(i, W) del.push_back('.');

	rep(i, H) {
		if (a[i] == del) {
			it = a.begin();
			it += i;
			a.erase(it);
			i--;
			H--;
		}
	}

	rep(j, W) {
		flag = true;

		rep(i, H) if (a[i][j] == '#') flag = false;
		if (flag) {
			rep(i, H) {
				sit = a[i].begin();
				sit += j;
				a[i].erase(sit);
			}
			j--;
			W--;
		}
	}

	rep(i, H) cout << a[i] << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define inf 1e18
int n,x,a[2222],b[2222],ans=inf,sum;
signed main(){
	cin>>n>>x;
	rep(i,n)cin>>a[i];
	rep(i,n)b[i]=inf;
	rep(i,n){//長さ
		rep(j,n)b[j]=min(b[j],a[(j+n-i)%n]);
		sum=0;
		rep(j,n)sum+=b[j];
		ans=min(ans,sum+i*x);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 384
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let p: Vec<i32> = (0..n).map(|_|  iter.next().unwrap().parse().unwrap()).collect();
    let mut ans: i32 = p.iter().sum();
    ans -= p.iter().max().unwrap() / 2;
    println!("{}",ans);
}


Measured memory_bytes: 4352
#include <iostream>

using namespace std;

int main()
{
    long long l,r;
    cin >> l >> r;
    if(r-l>=5000) r=l+5000;
    long long res=2019;
    for(long long o=l;o<=r;o++)
    {
        for(long long i=o+1;i<=r;i++)
        {
            res=min(res,(o*i)%2019ll);
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#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>

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

#define cauto const auto&
#else

#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 reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define double long double

#define MOD 1000000007LL
#define EPS 0
static const int INF=1<<24;
typedef complex<double> P;
typedef const P &rP;
typedef pair<P,P> seg;
vector<P> tri(3);
vector<P> aa(2);
double dot(rP a, rP b){
	// cout<<real(a)<<" "<<imag(a)<<" "<<real(b)<<" "<<imag(b)<<endl;
    return real(a) * imag(b) - imag(a) * real(b);
}
int check(P r){
	P a=tri[0]-tri[1],ar=r-tri[0];
	P b=tri[1]-tri[2],br=r-tri[1];
	P c=tri[2]-tri[0],cr=r-tri[2];
	double A=dot(a,ar),B=dot(b,br),C=dot(c,cr);
	// cout<<A<<" "<<B<<" "<<C<<endl;
	if(A>EPS&&B>EPS&&C>EPS) return 1;
	if(A<-EPS&&B<-EPS&&C<-EPS) return 1;
	return -1;
}
void mainmain(){
	int n;
	cin>>n;
	rep(i,n){
		rep(j,3){
			double a,b;
			cin>>a>>b;
			tri[j]=P(a,b);
		}
		rep(j,2){
			double a,b;
			cin>>a>>b;
			aa[j]=P(a,b);	
		}
		if(check(aa[0])*check(aa[1])<0){
			cout<<"OK\n";
		}
		else{
			cout<<"NG\n";
		}
	}
}



}
main() try{
    mainmain();
}
catch(...){
}

Measured memory_bytes: 1180
n, k = map(int, input().split())
h = [int(x) for x in input().split()]

inf = 10 ** 10
dp = [inf] * n
dp[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i+j >= n:
            break
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))
        
print(dp[n-1])

Measured memory_bytes: 52448
// AOJ 0526: Boat Travel
// 2017.9.1 bal4u@uu
// 2017.12.2

#include <stdio.h>
#include <string.h>

#define INF 0x1fffffff
#define N 105			// >= 100+2
#define MAX 11000		// >= N*N

typedef struct { int t, node; } QUE;
QUE que[MAX]; int qsize;

#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

void min_heapify(int i)
{
	int l, r, min;
	QUE qt;

	l = LEFT(i), r = RIGHT(i);
	if (l < qsize && que[l].t < que[i].t) min = l; else min = i;
	if (r < qsize && que[r].t < que[min].t) min = r;
	if (min != i) {
		qt = que[i]; que[i] = que[min]; que[min] = qt;
		min_heapify(min);
	}
}

void deq()
{
	que[0] = que[--qsize];
	min_heapify(0);
}

void enq(int n, int t)
{
	int i, min;
	QUE qt;
	i = qsize++;
	que[i].node = n, que[i].t = t;
	while (i > 0 && que[min = PARENT(i)].t > que[i].t) {
		qt = que[i]; que[i] = que[min]; que[min] = qt;
		i = min;
	}
}

typedef struct { int to[N], t[N]; } TBL;
TBL tbl[N];
int len[N];
int node[N];

char buf[50], *p;
int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	p++;
	return n;
}

int search(int start, int goal)
{
	int i, k, s, e;

	qsize = 0;
	memset(node, 0x55, sizeof(node));
	node[start] = 0;
	enq(start, 0);
	while (qsize) {
		s = que[0].node, deq();
		if (s == goal) break;
		for (i = 0; i < len[s]; i++) {
			e = tbl[s].to[i];
			k = node[s] + tbl[s].t[i];
			if (k < node[e]) node[e] = k, enq(e, k); 
		}
	}
	return node[goal];
}

int main()
{
	int n, k, a, b, e, t;

	while (fgets(p=buf, 50, stdin) && *p != '0') {
		n = getint(), k = getint();
		memset(len, 0, sizeof(len));
		while (k-- > 0) {
			fgets(p=buf, 50, stdin);
			if (*p & 1) {
				p += 2;
				a = getint(), b = getint(), e = getint();
				t = len[a], tbl[a].to[t] = b, tbl[a].t[t] = e, len[a]++;
				t = len[b], tbl[b].to[t] = a, tbl[b].t[t] = e, len[b]++;
			} else {
				p += 2;
				a = getint(), b = getint();
				if ((e = search(a, b)) > INF) e = -1; 
				printf("%d\n", e);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1732
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = 1e17 - 10;
const double PI = acos(-1);
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)
struct Edge { LL to, cost; };
LL h, w, n, m, s, t, k, ans = 0, a[100001], d[100001];
Ppll pp[200002];
vector<Edge>vec[100001];
int main() {
	cin >> n >> m >> t;
	cout << (n - m) % t << endl;
	return 0;
}


Measured memory_bytes: 4352
// AOJ 2466: Substring Expression
// 2017.11.13 bal4u@uu

#include <stdio.h>

int cnt[100005];
char buf[100005];

int main()
{
	int i;
	long long ans;
	char *p;
	
	fgets(p=buf, sizeof(buf), stdin);
	i = 0, ans = 0;
	while (*p > ' ') {
		if (*p++ == '(') i++; else i--;
		ans += cnt[i];
		cnt[i]++;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=101000;
bool vis[100];
char s[100];
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",s);
    int len=strlen(s);
    int sum=0;
    for(int i=2; i<len; i++)
    {
        if(s[i]=='C'&&s[i-1]=='B'&&s[i-2]=='A')
            sum++;
    }
    cout<<sum<<endl;
    return 0;
}
/*
3
10 3
1 2 3
0 1 2
100 7
3 4 5 6 7 8 9
1 2 3 4 5 6 7
10000 10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9
*/



Measured memory_bytes: 256
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;

int main()
{
   
   long long n;
   cin >> n;
   set<long long> s;
   for(long long i=0; i<n; i++){
       long long a;
       cin >> a;
       s.insert(a);
   }
   
   if(s.size() == n)
   cout << "YES\n";
   else
   cout << "NO\n";
   

    return 0;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh

//int t[100005] , x[100005] , y[100005];
int main(){
	dhoom;
	int a , b , c;
	cin >> a >> b >> c;
	int x;
	cin >> x;
	int ans = 0;
	for(int i = 0 ; i <= a ; i++){
			for(int j = 0 ; j <= b ; j++)
			{
					for(int k = 0 ; k <= c ; k++)
					{
						if(500*i + 100*j+50*k == x)
							ans++;
					}
			}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
 
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

#define MOD 1000000007LL

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


  cin >> a >> b >> c >> k;

  while (b<=a) {
    k--;
    if (k<0) break;
    b *= 2;
  }
  if (k<0) {
    cout << "No" << endl;
    return 0;
  }
  while (c<=b) {
    k--;
    if (k<0) break;
    c *= 2;
  }

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

  return 0;
}


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

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fm, to)    for (int i = fm; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 3e2;
int n, m, mod, dp[nsz + 5][nsz + 5], suf[nsz + 5][nsz + 5], C[nsz + 5][nsz + 5];

void inline init() {
    circ (i, 0, n) {
        C[i][0] = 1;
        cont (j, i) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }
}

void inline upd(int &a, int b) {
    (a += b) && a >= mod && (a -= mod);
}

int main() {
    scanf("%d%d%d", &n, &m, &mod);
    init();
    for (int i = m; i >= 0; --i) {
        dp[1][i] = 1;
        suf[1][i] = suf[1][i + 1] + dp[1][i];
    }
    circ (i, 2, n + 1) {
        for (int k = m; k >= 0; --k) {
            cont (j, i - 1) {
                upd(dp[i][k], (num) dp[i - j][k] * suf[j][k + 1] % mod * C[i - 2][j - 1] % mod);
            }
            upd(suf[i][k], suf[i][k + 1] + dp[i][k]);
        }
    }
    printf("%d\n", dp[n + 1][0]);
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<typename T>
void chmax(T &a,T b){
  if(a<b)a=b;
}
struct tree{
  vector<vector<int>> G,son,ancestor;
  vector<int> depth,parent;
  queue<int> que;
  int root=-1;
  bool made_lca=false;

  tree(int n):G(n),son(n),parent(n,-1),depth(n,0),ancestor(n){
    for(int i=0;i<n;i++)ancestor[i].resize(30);
  }

  void add_edge(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
  }

  void have_root(int r){
    root=r;
    depth[r]=-1;
    que.push(r);
    while(que.size()){
      int p=que.front();que.pop();
      for(int q:G[p]){
        if(parent[p]==q)continue;
        son[p].push_back(q);
        parent[q]=p;
        que.push(q);
      }
    }
  }

  void set_depth(){
    assert(~root);
    depth[root]=0;
    que.push(root);
    while(que.size()){
      int p=que.front();que.pop();
      for(int q:son[p]){
        depth[q]=depth[p]+1;
        que.push(q);
      }
    }
  }

  inline void make_lca(){
    assert(~root);
    if(depth[root]<0)set_depth();
    for(auto p:ancestor)for(auto &q:p)q=-1;
    for(int i=0;i<G.size();i++)ancestor[i][0]=parent[i];
    for(int j=1;j<30;j++)
      for(int i=0;i<G.size();i++)
        if(~ancestor[i][j-1])
          ancestor[i][j]=ancestor[ancestor[i][j-1]][j-1];
    made_lca=true;
  }

  int lca(int u,int v){
    if(!made_lca)make_lca();
    if(depth[u]>depth[v])swap(u,v);
    int diff=depth[v]-depth[u],cnt=0;
    while(diff){
      if(diff&1)v=ancestor[v][cnt];
      cnt++;
      diff>>=1;
    }
    if(u==v)return u;
    int high=25,low=-1;
    for(int k=25;k>=0;k--)if(ancestor[u][k]!=ancestor[v][k])u=ancestor[u][k],v=ancestor[v][k];
    return ancestor[u][0];
  }

};
signed main(){
  int n;cin>>n;int u,v;cin>>u>>v;u--;v--;swap(u,v);
  tree t(n);
  for(int i=1;i<n;i++){
    int a,b;cin>>a>>b;a--;b--;
    t.add_edge(a,b);
  }
  t.have_root(u);
  int ans=0;
  for(int i=0;i<n;i++){
    if(t.lca(i,v)==u)continue;
    int a=t.lca(i,v);
    if(t.depth[v]-t.depth[a]>t.depth[a])continue;
    //cout<<"I"<<i<<endl;
    chmax(ans,t.depth[i]-1);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 39936
import itertools
s = input()
a = ["", "+"]
a = list(itertools.product(a, repeat=len(s) - 1))
total = 0
for i in a:
    ss = ""
    for j in range(len(s)):
        ss += s[j]
        if j < len(i) and i[j] == "+":
            total += int(ss)
            ss = ""
    total += int(ss)
print(total)


Measured memory_bytes: 3064
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author yosiiii
 */


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

class CReplacingInteger {
public:
	void solve(std::istream& in, std::ostream& out) {
        ll n,k;
        in >> n >> k;
        out << min(n%k,abs(n-k*(n/k+1))) << endl;
	}
};


int main() {
	CReplacingInteger solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) {
            continue;
        }
        int tmp = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0) {
                tmp++;
            }
        }
        if (tmp == 8) {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#define BLACK 1
#define WHITE 0
#define GRAY -1
#define NUM 100
#define INF 1000000

int main(){
  int i,n,j,a[NUM][NUM],u,k,v,d[NUM],pi[NUM],color[NUM],minv;
  scanf("%d",&n);

  for(i=0;i<NUM;i++){
    for(j=0;j<NUM;j++){
      a[i][j]=INF;
    }
  }
  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    for(j=0;j<k;j++){
      scanf("%d",&v);
      scanf("%d",&a[u][v]);
    }
  }
  for(v=0;v<n;v++){
    d[v]=INF;
    pi[v]=-1;
    color[v]=WHITE;
  }
  d[0]=0;

  while(1){
    minv=INF;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK && d[i]<minv){
	minv=d[i];
	u=i;
      }
    }
    if(minv==INF){
      break;
    }
    color[u]=BLACK;
    for(v=0;v<n;v++){
      if(color[v]!=BLACK&&a[u][v]!=INF){
	if(d[u]+a[u][v]<d[v]){
	  pi[v]=u;
	  d[v]=d[u]+a[u][v];
	  color[v]=GRAY;
	}
      }
    }
  }
  for(i=0;i<n;i++){
    printf("%d ",i);
    if(d[i]==INF){
      printf("%d\n",-1);
    }else{
      printf("%d\n",d[i]);
    }
  }
  return 0;
}



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

using ll = long long;

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

  c -= (a + b);
  cout << (c > 0 && 4 * a * b < c * c ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <stack>
#include <cassert>
using namespace std;
typedef long long LL;
const int M = 1e6 + 5;
const int N = 100000 + 5;
const LL mod = 19260817;
const int MAX = 5e5 + 5;
const int MAXV = 100000 + 5;
const LL INF = (1LL << 62);
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.);
int a[N];
int main() {
#ifdef local
    freopen("input", "r", stdin);
//    freopen("w", "w", stdout);
//    freopen("input", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)cin >> a[i];
    sort(a, a + n);
    if(a[n - 1] - a[0] > 1) {
        cout << "No" << endl;
    } else {
        if(a[0] == a[n - 1]) {
            if(a[0] * 2 <= n || a[0] == n - 1)
                cout << "Yes" << endl;
            else cout << "No" << endl;
        } else {
            int sm = 0;
            for(int i = 0; i < n; i++) {
                if(a[i] == a[0])sm++;
            }
            if((a[n - 1] - sm) * 2 <= (n - sm) && a[n - 1] > sm) {
                cout << "Yes" << endl;
            } else cout << "No" << endl;

        }
    }
}



Measured memory_bytes: 640
from collections import defaultdict


def main():
    dic = defaultdict(lambda: 0)
    _ = input()
    d_list = [int(i) for i in input().split()]
    for d in d_list:
        dic[d] += 1

    flag = True
    _ = input()
    m_list = [int(i) for i in input().split()]
    for m in m_list:
        dic[m] -= 1
        if dic[m] < 0:
            flag = False
            break
    if flag: print("YES")
    else: print("NO")


if __name__ == "__main__":
    main()

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

int main(){
	int i,j,n,a[101][101];
	while(scanf("%d",&n)==1&&n){
		memset(a,0,sizeof(a));
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				scanf("%d",&a[i][j]);
				a[i][n] += a[i][j];
				a[n][j] += a[i][j];
				a[n][n] += a[i][j];
			}
		}
		for(i=0;i<=n;i++){
			for(j=0;j<=n;j++){
				printf("%5d",a[i][j]);
			}
			puts("");
		}
	}
	return 0;
}

Measured memory_bytes: 1092
#include <stdio.h>

int main() {
	int a, b;

	scanf("%d %d", &a ,&b);

	if (a < b) {
		printf("a < b\n");
	} else if (a > b) {
		printf("a > b\n");
	}
	else if(a == b) {
		printf("a == b\n");
	}
	else

	return 0;
}


Measured memory_bytes: 2108
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
    int b[110];
    int n,m,c;
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=m;i++)
        scanf("%d",&b[i]);

        int ans=0,res,x;
    for(int i=1;i<=n;i++)
    {
        res=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&x);
            res+=b[i]*x;
        }
        if(res+c>0)ans++;
    }
    printf("%d\n",ans);
   return 0;

}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<climits>
#include<cstdlib>
#include<map>
#include<math.h>
#include<utility>
using namespace std;
int main(){
  int n;
  long long int a[20000];
  cin >> n;
  for(int i=0; i<n; i++) cin >> a[i];

  int cnt = 0;
  for(int i=0; i<n; i++){
    int tmp = a[i];
    while(1){
      if(tmp % 2 == 0){
        cnt++;
        tmp = tmp / 2;
      }else{
        break;
      }
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int find(int a[],int l,int r)
{
    int max=a[l];
    int pos=l;
    for(int i=l;i<=r;i++)
    {
        if(a[i]>=max)
        {
            max=a[i];
            pos=i;
        }
    }
    return pos;
}
void change(int a[],int i)
{
    int temp1=a[i];
    int temp2=a[i+1];
    int temp3=a[i+2];
    a[i]=temp3;
    a[i+1]=temp1;
    a[i+2]=temp2;
}
// Return n'th term of a series defined using belo
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll a[n+1];
    for(int i=1;i<=n;i++)
        a[i]=1;
    for(int i=2;i<=n;i++)
    {
        int k=i;
        while(k<=n)
        {
            a[k]+=1;
            k+=i;
        }
    }
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=i*a[i];
    }
    cout<<sum<<"\n";
}





Measured memory_bytes: 81724
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

N = gete(int)
h = geta(int)

dp = [0 for _ in range(N)]
dp[0], dp[1] = 0, abs(h[0] - h[1])

for i in range(2, N):
    dp[i] = min(dp[i - 2] + abs(h[i] - h[i - 2]),
                dp[i - 1] + abs(h[i] - h[i - 1]))

print(dp[N - 1])


Measured memory_bytes: 13924
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

namespace {  // 名前なし名前空間
	// gcd, lcm は C++17 でstdに標準入りしたので言語のバージョンに注意
	// 最大公約数
	ll gcd(ll a, ll b) {
		if (b == 0) return a;
		return gcd(b, a % b);
	}

	// 最小公倍数
	ll lcm(ll a, ll b) {
		return a / gcd(a, b) * b;
	}
}

int main() {

	ll n, m;
	cin >> n >> m;
	vector<pair<ll, ll>> ab(n);
	rep(i, n) cin >> ab[i].first >> ab[i].second;

	sort(allof(ab));

	ll ans = 0;
	priority_queue<ll> pq;
	int left = 0;

	for (int remain = 1; remain <= m; remain++) {
		//cout << remain << " " << ans << endl;
		while (left < n && ab[left].first <= remain)
		{
			pq.push(ab[left].second);
			left++;
			if (left == n) break;
		}
		if ((int)pq.size() != 0) {
			ans += pq.top();
			pq.pop();
		}
	}

	cout << ans << endl;

	return 0;
}

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

using namespace std;

int main()
{
    string s,t;
    int count=0;
    cin >> s;
    cin >> t;

    for(int i=0;i<3;i++)
        if(s[i]==t[i])count++;
    cout << count << endl;
    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main (String[] args) {
        Scanner scan = new Scanner(System.in);
        String str;
        double a, b;
        str = scan.next();
        a = Double.parseDouble(str);
        str = scan.next();
        b = Double.parseDouble(str);
        scan.close();

        if (a == b) {
            System.out.println("a == b");
        } else if (a > b){
            System.out.println("a > b");
        } else if (a < b) {
            System.out.println("a < b");
        }
    }
}


Measured memory_bytes: 26184