akhauriyash/Code-Regression huggingface dataset:
Imports System.Console
Module Module1
    Dim n As Integer
    Sub Main()
        n = ReadLine()
        Dim r(n) As String
        For i = 1 To n
            r(i) = ReadLine()
        Next
        Dim AC, WA, TLE, RE As Integer
        For i = 1 To n
            Select Case r(i)
                Case "AC"
                    AC += 1
                Case "WA"
                    WA += 1
                Case "TLE"
                    TLE += 1
                Case "RE"
                    RE += 1
            End Select
        Next
        WriteLine("AC x " & AC)
        WriteLine("WA x " & WA)
        WriteLine("TLE x " & TLE)
        WriteLine("RE x " & RE)
    End Sub
End Module


Measured memory_bytes: 32448
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <cstdio>
using namespace std;
typedef long long ll;

int gcd(int a,int b){
    int t;
    while(b>0){
        t=b;
        b=a%b;
        a=t;
    }
    return a;
}

int lcm(int a,int b){
    return a*b/gcd(a,b);
}

int main(){
    ll a,b,c,d,e,k,l,m,n,o=0,p,q,x,y,z,max1=0,ans=0;
    string s,t,u;
    cin>>a>>b>>c;
    
    ans=c-(a-b);
    if(ans<0)ans=0;
    cout<<ans<<endl;
}




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

int main () {
    string a;
    cin >> a;
    if (a == "SUN")
        cout << 7 << endl;
    else if (a == "MON")
        cout << 6 << endl;
    else if (a == "TUE")
        cout << 5 << endl;
    else if (a == "WED")
        cout << 4 << endl;
    else if (a == "THU")
        cout << 3 << endl;
    else if (a == "FRI")
        cout << 2 << endl;
    else if (a == "SAT")
        cout << 1 << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intMax 
    static final int INF = 1_000_000_000; // 10^9  
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		int num = saori.saori_hayami() + saori.saori_hayami();
		System.out.println(6 - num);
		
		saori.close();
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

Measured memory_bytes: 21588
x, y = map(int, input().split())

a=b=0


if x*4<y or x*2>y:
    print('No')
    exit()

if (y-2*x)%2==0:
    n=(y-2*x)/2
    if x-b>=0:
        print('Yes')
else:
    print('No')

Measured memory_bytes: 9184
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define rrep1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
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 n, m, k;

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};


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

    UnionFind tree(n);
    vector<int> nFriend(n, 0), nBlock(n, 0);

    rep(i, m) {
        int a, b; cin >> a >> b;
        a--; b--;
        tree.merge(a, b);
        nFriend[a]++;
        nFriend[b]++;
    }
    rep(i, k) {
        int a, b; cin >> a >> b;
        a--; b--;
        if (tree.issame(a, b)) {
            nBlock[a]++;
            nBlock[b]++;
        }
    }

    rep(i, n) {
        int n1 = nFriend[i];
        int n2 = nBlock[i];
        int n3 = n - tree.size(i);
        cout << n - (n1+n2+n3) - 1;
        if (i < n-1) cout << " ";
        else cout << endl;
    }
}


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

int main(){
  long k;
  cin>>k;
  int m=7%k;
  long msum=m;
  for(long i=0;i<k;i++){
    if(msum==0){
      cout<<i+1;
      return 0;
    }
    m=m*10%k;
    msum+=m;
    msum%=k;
  }
  cout<<-1;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int A,B;
    cin >> A >>B;
    int count=0;
    if(B==1)
    {
      cout << 0 << endl;
      return 0;
    }
    for(int i=1; ;i++)
    {
        if(B<=A*i-(i-1))
        {
            count=i;
            break;
        }
    }
    cout << count <<endl;
}


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

using namespace std;

#define NIL -1
#define roop(x,a,b) for(int x=a;x<b;x++)
#define max(a,b) (a > b ? a : b)

typedef struct{
    int parent;
	int right;
	int left;
	int depth;
	int height;
	int sibling;
}node;

vector<node> u;

int setHeight(int id){
	int hr = 0;
	int hl = 0;
	if(u[id].right != NIL){
		hr = setHeight(u[id].right) + 1;
	}
	if(u[id].left != NIL){
		hl = setHeight(u[id].left) + 1;
	}
	return u[id].height = max(hr,hl);
}

void setDepth(int id,int d){
	u[id].depth = d;
	if(u[id].right != NIL)setDepth(u[id].right,d+1);
	if(u[id].left != NIL)setDepth(u[id].left,d+1);
}

void setSibling(int id,char flag){
	if(!flag){
		u[id].sibling = NIL; 
	}
	if(u[id].right != NIL){
		u[u[id].right].sibling = u[id].left;
		setSibling(u[id].right,1);
	}
	if(u[id].left != NIL){
		u[u[id].left].sibling = u[id].right;
		setSibling(u[id].left,1);
	}
}

int main(void){
	int n;
	cin >> n;
	u.resize(n);
	roop(i,0,n){
		u[i].parent = NIL;
	}
	roop(i,0,n){
		int id,l,r;
		cin >> id >> l >> r;
		u[id].right = r;
		u[id].left = l;
		if(u[id].right != NIL)u[r].parent = id;
		if(u[id].left != NIL)u[l].parent = id;
	}
	roop(i,0,n){
		if(u[i].parent == NIL){
			setHeight(i);
			setDepth(i,0);
			setSibling(i,0);
		}
	}
	roop(i,0,n){
		int deg = 0;
		printf("node %d: parent = %d, ",i,u[i].parent);
		if(u[i].right != NIL)deg++;
		if(u[i].left != NIL)deg++;
		printf("sibling = %d, degree = %d, ",u[i].sibling,deg);
		printf("depth = %d, height = %d, ",u[i].depth,u[i].height);
		if(u[i].parent == NIL){
			printf("root\n");
		}else if(deg == 0){
			printf("leaf\n");
		}else{
			printf("internal node\n");
		}
	}
	return 0;
}


Measured memory_bytes: 3240
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
const ll MOD=1000000007;
const ll INF=1<<29;
int main(){
    int n,m;cin >> n >> m;
    int x[m];
    rep(i,m)cin>>x[i];
    sort(x,x+m);
    vector<int> d(m-1);
    if(n<m){
    rep(i,m-1)d[i]=x[i+1]-x[i];
    sort(all(d),greater<int>());
    int ans=0;
    for(int i=n-1;i<m-1;i++){
        ans+=d[i];
    }
    cout << ans << endl;
    }
    else cout << 0 << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<math.h>
int main()
{
	long long int n,i,t;
	long long int sum=0;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
    {
        t=i;
        if(t%3==0||t%5==0)
        {
            t=0;
        }
        sum=sum+t;
    }

    printf("%lld",sum);
}


Measured memory_bytes: 1724
x=[]
u=[]
n=int(input())
for i in range(n):
    a,b=map(str,input().split())
    x.append(float(a))
    u.append(b)
ans=0
for i in range(n):
    if u[i]=='BTC':
        ans+=x[i]*380000
    else:
        ans+=x[i]
print(ans)

Measured memory_bytes: 3060
n, w = map(int, input().split())
g = []
for i in range(n):
    g.append(list(map(int, input().split())))
m = [[0 for j in range(w+1)]for i in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j-g[i][0] < 0:
            m[i+1][j] = m[i][j]
        else:
            m[i+1][j] = max(m[i][j], m[i][j-g[i][0]]+g[i][1])
print(m[n][w])

Measured memory_bytes: 171656
fun main(args:Array<String>?): Unit {
    while(true){
        val (d, w)  = readLine()!!.trim().split(' ').map(String::toInt)
        if (d == 0 && w == 0) return
        val state = Array(d){readLine()!!.trim().split(' ').map(String::toInt).toIntArray()}
        println((2 until w).mapNotNull{right -> (0 until right - 1).mapNotNull{left -> (2 until d).mapNotNull{bottom -> (0 until bottom - 1).mapNotNull{top -> calSpace(state, left, right, top, bottom)}.max()}.max()}.max()}.max() ?: 0)
    }
}
fun calSpace(state: Array<IntArray>, left: Int, right: Int, top: Int, bottom: Int): Int? {
    val min = listOfNotNull((left .. right).map{i -> Math.min(state[top][i], state[bottom][i])}.min(), (top .. bottom).map{i -> Math.min(state[i][left], state[i][right])}.min()).min() ?: 0
    return (left + 1 until right).flatMap{x -> (top + 1 until bottom).map{y -> state[y][x]}}.let{depth ->
        if (depth.all{min > it}) depth.map{min - it}.sum()
        else null
    }
}


Measured memory_bytes: 75184
// ######      ###      #######    #######    ##     #     #####        ###     ##### //
// #     #    #   #          #        #       # #    #    #     #      #   #     ###  //
// #     #   #     #        #         #       #  #   #   #       #    #     #    ###  //
// ######   #########      #          #       #   #  #   #           #########    #   //
// #     #  #       #     #           #       #    # #   #    ####   #       #    #   //
// #     #  #       #    #            #       #     ##   #    #  #   #       #        //
// ######   #       #   #######    #######    #      #    #####  #   #       #    #   //

// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> ppl;
#define ain(a,n) for(ll i=0;i<(n);++i)	cin>>(a)[i];
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define loop(i,n) for(ll i=0;i<(n);++i)
#define FOR(i,a,b) for(ll i=(a);i<=(b);++i)
#define FORD(i,a,b) for(ll i=(a);i>=(b);--i)
#define cases ll T=0;cin>>T;while(T--)
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define END "\n"
#define pb push_back
#define mp make_pair
#define go(c,itr) for(auto itr=(c).begin(); itr!=(c).end(); ++itr)
#define back(c,itr) for(auto itr=(c).rbegin(); itr!=(c).rend(); ++itr)
#define PI 3.14159265359
#define inf 9e18
#define MOD 1000000007
#define MODU 998244353
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define MAXN 1000005
const string alpha = "abcdefghijklmnopqrstuvwxyz";
const ll N = 1005;
const long double epsilon = 1e-9;
ll binexp(ll a, ll b, ll m) {
	a %= m;
	ll res = 1;
	while (b > 0) {
		if (b & 1)
			res = res * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return res;
}
ll modinvfermat(ll a, ll m)
{
	return binexp(a, m - 2, m);
}
void task(bool flag)
{
	if (flag)
		cout << "YES\n";
	else
		cout << "NO\n";
}
ll lcm(ll a, ll b)
{
	return ((1LL * a * b) / (__gcd(a, b)));
}

signed main() {

	fast
	ll n;
	cin >> n;
	if (n % 1000 == 0)
		cout << 0 << END;
	else
		cout << 1000 - n % 1000 << END;


// #ifndef ONLINE_JUDGE
// 	cout << "\nTime Elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec\n";
// #endif
	return 0;
}

Measured memory_bytes: 3664
N = int(input())
A = list(map(int, input().split()))

index = []
if N % 2 == 0:
    for i in range(N - 1, 0, -2):
        index.append(i)
    for j in range(0, N - 1, 2):
        index.append(j)
else:
    for i in range(N - 1, -1, -2):
        index.append(i)
    for j in range(1, N - 1, 2):
        index.append(j)

B = []
for i in index:
    B.append(str(A[i]))
print(' '.join(B))


Measured memory_bytes: 40004
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
ikeruheya = [[] for i in range(n)]
ans = [0]*(n+1)

ans[0]=-1
ans[1]=1
for i in range(m):
    if a[i][0]==1:
        ikeruheya[0].append(a[i][1])
    elif a[i][1]==1:
        ikeruheya[0].append(a[i][0])
    else:
        ikeruheya[a[i][0]-1].append(a[i][1])
        ikeruheya[a[i][1]-1].append(a[i][0])

#print(ikeruheya)
next=[1]
count = 1
while count < n and len(next)!=0:
    
    imaheya = next.pop(0)
    j = 0
    while j < len(ikeruheya[imaheya-1]) and count < n:
    
        if ans[ikeruheya[imaheya-1][j]]==0:
            ans[ikeruheya[imaheya-1][j]]= imaheya             
            next.append(ikeruheya[imaheya-1][j])
            count += 1
            j+=1
        else:
            j+=1


print("Yes")
for i in range(2, n+1):
    print(ans[i])


    
    


Measured memory_bytes: 58060
N = int(input())
mod = N % 10
if mod == 2 or mod == 4 or mod == 5 or mod == 7 or mod == 9:
    print("hon")
elif mod == 0 or mod == 1 or mod == 6 or mod == 8:
    print("pon")
else:
    print("bon")


Measured memory_bytes: 61560
from heapq import heappop,heappush
from collections import defaultdict

n,m = map(int,input().split())
data = defaultdict(list)
for _ in range(n):
    a,b = map(int,input().split())
    data[a].append(b)

ans = 0
h_queue =[]
for i in range(1,m+1):
    for j in data[i]:
        heappush(h_queue,-j)
    if len(h_queue) > 0:
        ans -= heappop(h_queue)

print(ans)

Measured memory_bytes: 27684
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)



n,m = map(int, input().split())
f = []

for x in range(m):
    ff = []
    a,b = map(int, input().split())
    ff.append(a)
    ff.append(b)
    f.append(ff)

uf = UnionFind(n)

for i in range(m):
    a = f[i][0] - 1
    b = f[i][1] - 1
    uf.union(a, b)

ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))

print(ans)


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

#define pb push_back
#define all(a) (a).begin(), (a).end()

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

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int k; cin >> k;
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    if (k <= 12) {
        cout << k << '\n';
        return 0;
    }

    for (int i = 1; i <= 9; ++i)
        pq.push(i);

    int done = 0;
    while (true) {
        ll cur = pq.top();
        pq.pop();
        ++done;

        if (done == k) {
            cout << cur << '\n';
            break;
        }

        int d = cur % 10;
        pq.push((cur * 10) + d);
        if (d != 0)
            pq.push((cur * 10) + d - 1);
        if (d != 9)
            pq.push((cur * 10) + d + 1);
    }
}

Measured memory_bytes: 2420
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))
mod = 10**9+7

res = 0

ans = 0
al = sum(lst1)
for i in lst1:
    res += i
    ans += (al-res)*i
    ans %= mod

    

print(ans)

Measured memory_bytes: 100720
// 解説後
#include <iostream>

// 末尾の0の個数 = 10で割り切れる回数
//
// Nが奇数のとき、f(N)は10で割り切れないので、末尾の0の個数は0
//
// Nが偶数のとき、f(N) = \prod_{i=1}^{N/2}(2i)
// このとき、f(N)が2で割り切れる回数は十分に大きいので、
// f(N)が10で割り切れる回数はf(N)が5で割り切れる回数に等しい
//
// 5でn回だけ割り切れる値は{5,5^2,5^3,...,5^n}のすべてで割り切れる
// => {1,2,3,...,N/2}のうち5^iで割り切れる値の個数はN/2/5^i
// => f(N)が5で割り切れる回数はΣ(N/2/5^i)になる
int main() {
  uint64_t N;
  std::cin >> N;

  if (N % 2 != 0) {
    std::cout << '0';
  } else {
    uint64_t result = 0;
    for (uint64_t i = 10; i <= N; i *= 5) {
      result += N / i;
    }
    std::cout << result;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

//ABC122 C

int n,q;
string s;

int main(){
	cin>>n>>q>>s;
	vi a(n);
	for(int i=0;i<n;i++) if(s[i]=='A'&&s[i+1]=='C') a[i+1]++;
	for(int i=1;i<n;i++) a[i]+=a[i-1];
	for(int i=0;i<q;i++){
		int l,r;
		cin>>l>>r;
		cout<<a[r-1]-a[l-1]<<endl;
	}
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

int main(){
  string s;
  cin>>s;
  int ans=0;
  for(int i=0;i<s.size();i++){
    int sum=0;
    for(int j=i;j<s.size();j++){
	 if(s[j]=='A'||s[j]=='C'||s[j]=='G'||s[j]=='T')sum++;
	 else break;
    }
    ans=max(ans,sum);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#define MAX 100005
#define NIL -1

using namespace std;

struct Node {
    int p, l, r;
};

Node T[MAX];
int n, D[MAX];

/*void print(int u) {
    int i, c;
    cout << "node" << u << ": ";
    cout << "parent = " << T[u].p << ", ";
    cout << "depth = " << D[u] << ", ";

    if (T[u].p == NIL) cout << "root, ";
    else if (T[u].l == NIL) cout << "leaf, ";
    else cout << "internal node, ";

    cout << "[";
    for (i = 0, c = T[u].l; c != NIL; i++, c = T[c].r) {
        if (i > 0) cout << ", ";
        cout << c;
    }
    cout << "]" << endl;
}
*/
void print(int u){
    cout << "node " << u << ": ";
    cout << "parent = " << T[u].p << ", ";
    cout << "depth = " << D[u] << ", ";

    if(T[u].p == NIL)       cout << "root";
    else if(T[u].l == NIL)  cout << "leaf";
    else                    cout << "internal node";
    cout << ", ";

    cout << "[";

    int c;
    for(int i = 0, c = T[u].l; c != NIL; i++, c = T[c].r){
        if(i) cout << ", ";
        cout << c;
    }
    cout << "]" << endl;
}


void rec(int u, int p) {
    D[u] = p;
    if (T[u].l != NIL) rec(T[u].l , p + 1);
    if (T[u].r != NIL) rec(T[u].r, p);
}

int main() {
    int v, d, c, l, r;
    cin >> n;
    for (int i = 0; i < n; i++) {
        T[i].p = T[i].l = T[i].r = NIL;
    }

    for (int i = 0; i < n; i++) {
        cin >> v >> d;
        for (int j = 0; j < d; j++) {
            cin >> c;
            if (j == 0) {
                T[v].l = c;
            } else {
                T[l].r = c;
            }
            l = c;
            T[c].p = v;
        }
    }

    for (int i = 0; i < n; i++) {
        if (T[i].p == NIL) r = i;
    }
    rec(r, 0);

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


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

int dp[1001][1001];
string str1, str2;
int n;

int solve(string str1, string str2) {
  memset(dp, 0, sizeof(dp));
  for(int r = 0; r < str2.size(); r++) {
    for(int c = 0; c < str1.size(); c++) {
      if(str2[r] == str1[c]) {
        dp[r + 1][c + 1] = dp[r][c] + 1;
      }
      else {
        dp[r + 1][c + 1] = max(dp[r + 1][c], dp[r][c + 1]);
      }
    }
  }
  return dp[str2.size()][str1.size()];
}

int main() {
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> str1 >> str2;
    cout << solve(str1, str2) << endl;
  }
}



Measured memory_bytes: 7040
from itertools import chain


def main():
    N, M, K = map(int, input().split())

    A = map(int, input().split())
    B = list(map(int, input().split()))

    answer = 0

    sum_b = sum(B)
    idx_b = M
    remain = K

    for i, a in enumerate(chain([0], A)):
        remain -= a
        if remain < 0:
            break

        while sum_b > remain and idx_b >= 0:
            idx_b -= 1
            b = B[idx_b]
            sum_b -= b

        i += idx_b
        answer = i if answer < i else answer

    print(answer)


if __name__ == "__main__":
    main()


Measured memory_bytes: 48396
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using System.IO.Pipes;

public class HelloWorld
{
    static bool res = false;
    static public void Main()
    {
        //var NL = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        var N = long.Parse(Console.ReadLine());

        var ans = false;
        var count = 0;
        for (int i = 0; i < N; i++)
        {
            var D = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
            if (D[0] == D[1])
            {
                count++;
            }
            else
            {
                count = 0;
            }

            if(count >= 3)
            {
                ans = true;
            }
        }

        Console.WriteLine(ans ? "Yes":"No");
    }
}


Measured memory_bytes: 28252
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
int main (){
    int a;
    cin >> a;
    int ans = 0;
    if (a%10==1) ans++;
    if (a/100==1)ans++;
    if (a/10%10==1)ans++;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define int long long
#define all(c) c.begin(), c.end()
#define FAST ios_base::sync_with_stdio(false) , cin.tie(NULL);
#define pb push_back
#define F first
#define S second
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define one(x) cout<<#x<<" : "<<x<<endl;
#define two(x,y) cout<<#x<<" : "<<x<<" , "<<#y<<" : "<<y<<endl;
#define three(x,y,z) cout<<#x<<" : "<<x<<" , "<<#y<<" : "<<y<<" , "<<#z<<" : "<<z<<endl;
#define PI acos(-1)
const int M = 1000000007;
const int N=3e5+5;

void solve()
{
    int x;
    cin >> x;
    int coins = 0;

    int ans;
    ans = x/500 ;
    coins +=500*ans*2;
    ans = x - ans*500;
    coins +=5*(ans/5);
    cout<<coins<<endl;
}
signed main()
{
    int tc;
//    cin >> tc;
    tc = 1;
    while(tc--)
        solve();
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
using namespace std;

int main()
{
  int n,ans;
  cin>>n;
  if(n<=104){
    ans=0;
  }else if(n<=134){
    ans=1;
  }else if(n<=164){
    ans=2;
  }else if(n<=188){
    ans=3;
  }else if(n<=194){
    ans=4;
  }else{
    ans=5;
  }
  cout<< ans <<endl;
}


Measured memory_bytes: 256
from collections import deque

def only_color(s):
  temp = s[0]
  for i in range(1, len(s)):
    c = s[i]
    if temp != c:
      return False
    temp = c

  return True

def new_color(s, i):
  color = [c for c in ("r", "g", "b") if c not in (s[i], s[i + 1])][0]
  return s[:i] + color * 2 + s[i + 2:]

def solve(s):
  if only_color(s):
    print(0)
    return
  length = len(s)
  dic = {}
  que = deque()
  que.append((s, 0))

  while que:
    colors, score = que.popleft()
    score += 1
    temp = colors[0]
    for i in range(1, length):
      ci = colors[i]
      if ci != temp:
        new = new_color(colors, i - 1)
        if only_color(new):
          print(score)
          return
        if new not in dic:
          dic[new] = score
          que.append((new, score))
      temp = ci
  else:
    print("NA")

def main():
  while True:
    s = input()
    if s == "0":
      break
    solve(s)

main()


Measured memory_bytes: 7820
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuffer sb = new StringBuffer(s);
        String kai = sb.reverse().toString();
        if(!s.equals(kai)){
            System.out.println("No");
            return;
        }
        String s2 = s.substring(0, (s.length()-1)/2);
        StringBuffer sb2 = new StringBuffer(s2);
        String kai2 = sb2.reverse().toString();
        if(!s2.equals(kai2)){
            System.out.println("No");

            return;
        }
        String s3 = s.substring(((s.length()+3)/2)-1 , s.length());
        StringBuffer sb3 = new StringBuffer(s3);
        String kai3 = sb3.reverse().toString();
        if(!s3.equals(kai3)){
            System.out.println("No");

            return;
        }
        System.out.println("Yes");
    }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

#define PB push_back
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define PII pair<int,int>
#define VS vector<string>
#define VI vector<int>
#define ll long long
#define ull unsigned long long
#define FST first
#define SEC second
int main(){
  VI V;
  REP(i,12){
    int a;cin>>a;V.PB(a);
  }
  sort(ALL(V));
  if(V[0]==V[1]&&V[0]==V[2]&&V[0]==V[3]&&
     V[4]==V[5]&&V[4]==V[6]&&V[4]==V[7]&&
     V[8]==V[9]&&V[8]==V[10]&&V[8]==V[11]){
    cout<<"yes"<<endl;
  }else{
    cout<<"no"<<endl;
  }
  return 0;
}

Measured memory_bytes: 3112
# coding: utf-8

n = int(input())

s = []
for i in range(n):
    s.append(''.join(sorted(input())))

s.sort()
num = 0
i = 0
while i < n - 1:
    if s[i] == s[i+1]:
        m = 1
        i += 1
        while i < n - 1 and s[i] == s[i+1]:
            m += 1
            i += 1
        if m == 1:
            num += m
        else:
            num += int(m*(m+1)/2)
    i += 1
            

print(num)

Measured memory_bytes: 10640
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
const int INF = 0x7fffffff;
using lll = long long;
using ull = unsigned long long;
using namespace std;


int main(){
  lll ii,jj,kk;
  vector<int> ret;
  string s;
  cin >> s;

  if(s[s.size()-1] == 's'){
    cout << s + "es" << endl;
  }
  else{
    cout << s + "s" << endl;
  }

  return 0;
}


Measured memory_bytes: 3604
n, m = map(int , input().split())
# L = []
# R = []

l_max = 0
r_min = 10 ** 6
for _ in range(m):
    l, r = map(int, input().split())
    if l_max < l:
        l_max = l
    if r < r_min:
        r_min = r
if l_max <= r_min:
    print(r_min - l_max + 1)
else:
    print(0)

Measured memory_bytes: 3060
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br =
				new BufferedReader(new InputStreamReader(System.in));

		while (true) {
			int n = Integer.parseInt(br.readLine());
			if (n == 0) break;
			int[][] nums = new int[n + 1][n + 1];
			for (int i = 0; i < n; i++) {
				String[] str = br.readLine().split(" ");
				for (int j = 0; j < n; j++)
					nums[i][j] = Integer.parseInt(str[j]);
			}
			for (int i = 0; i < n; i++) {
				int sum = 0;
				for (int j = 0; j < n; j++)
					sum += nums[i][j];
				nums[i][n] = sum;
			}
			for (int i = 0; i < nums.length; i++) {
				int sum = 0;
				for (int j = 0; j < n; j++)
					sum += nums[j][i];
				nums[n][i] = sum;
			}
			for (int i = 0; i < nums.length; i++) {
				System.out.printf("%5d", nums[i][0]);
				for (int j = 1; j < nums.length; j++)
					System.out.printf("%5d", nums[i][j]);
				System.out.println();
			}
		}

	}

}

Measured memory_bytes: 20772
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#include<stack>
#include<queue>
#include<list>
#include<bitset>

#define FOR(i, a, b) for(int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000

using namespace std;

int main(void){
	int a, b;
	bool flag = false;
	cin >> a >> b;
	if (b <= 9) {
		b = b + a * 10;
	}
	else if (b <= 99) {
		b = b + a * 100;
	}
	else {
		b = b + a * 1000;
	}
	for (int i = 1; i*i <= b; i++) {
		if (b == i*i) {
			flag = true;
		}
	}
	if (flag) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <iostream>
#include <functional>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <cmath>
#include <limits>
#include <tuple>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()



int main()
{
	int N;
	cin >> N;
	deque<int> ans;
	bool right = true;
	rep(i, N) {
		int a;
		cin >> a;
		if (ans.empty())
			ans.push_back(a);
		else {
			if (right) {
				ans.push_back(a);
			}
			else {
				ans.push_front(a);
			}
		}
		right = !right;
	}
	if (!right)
		reverse(ans.begin(), ans.end());
	rep(i, (int)ans.size()) {
		if (i > 0)
			cout << " ";
		cout << ans[i] ;
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 2944
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

int main(void) {
  int N, M, Q;
  cin >> N >> M >> Q;
  vector<vector<int>> train(N + 1, vector<int>(N + 1, 0));
  rep(i, M) {
    int L, R;
    cin >> L >> R;
    train[L][R]++;
  }
  rep(i, N) {
    rep(j, N) { train[i + 1][j + 1] += train[i + 1][j]; }
  }
  rep(i, N) {
    rep(j, N) { train[i + 1][j + 1] += train[i][j + 1]; }
  }

  rep(i, Q) {
    int p, q;
    cin >> p >> q;
    int answer =
        train[q][q] - train[q][p - 1] - train[p - 1][q] + train[p - 1][p - 1];
    cout << answer << endl;
  }
  return 0;
}

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

#ifdef SG
	#include <debug.h>
#else
	template<typename T> struct outputer;
	struct outputable {};
	#define PRINT(...)
	#define OUTPUT(...)
	#define show(...)
	#define debug(...)
	#define deepen(...)
	#define timer(...)
	#define fbegin(...)
	#define fend
	#define pbegin(...)
	#define pend
#endif

#define ARG4(_1,_2,_3,_4,...) _4

#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)

#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)

#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb emplace_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

typedef long double ld;
typedef int64_t ll;
typedef uint64_t ull;
typedef uint32_t ui;
typedef uint16_t us;
typedef uint8_t uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;

template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}

struct Input {
	ll n, a, b;
	
	bool read () {
		return !!(cin >> n >> a >> b);
	}

	void init (const Input &input) {
		*this = input;
	}
};

struct Data: Input {
	ll ans;
	
	void write () {
		cout << ans << endl;
	}
};


namespace Main {
	
	struct Solution: Data {
		
		void solve () {
			if (b < a) {
				ans = 0;
				return;
			}
			if (n == 1 && a != b) {
				ans = 0;
				return;
			}
			ans = (n - 2) * (b - a) + 1;
		}
		
		void clear () {
			*this = Solution();
		}
	};
}


Main::Solution sol;

int main () {
	cout.setf(ios::showpoint | ios::fixed);
	cout.precision(20);

	#ifdef SG
		freopen((problemname + ".in").c_str(), "r", stdin);
//		freopen((problemname + ".out").c_str(), "w", stdout);
		while (sol.read()) {
			sol.solve();
			sol.write();
			sol.clear();
		}
	#else
		sol.read();
		sol.solve();
		sol.write();
	#endif
	
	/*
	int t;
	cin >> t;
	forn (i, t) {
		sol.read();
		sol.solve();
		sol.write();
		sol.clear();
	}
	*/
	
	return 0;
}


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

int main() {
    int h, w;
    cin >> h >> w;

    vector<vector<char>> s(h+2, vector<char>(w+2, '.'));
    for (int i=1; i<h+1; i++) {
        for (int j=1; j<w+1; j++) {
            cin >> s.at(i).at(j);
        }
    }

    for (int i=1; i<h+1; i++) {
        for (int j=1; j<w+1; j++) {
            int bcnt=0;
            if (s.at(i).at(j) != '#') {
                for (int x=-1; x<=1; x++) {
                    for (int y=-1; y<=1; y++) {
                        if (s.at(i+x).at(j+y)=='#') bcnt++;
                    }
                }
                s.at(i).at(j)='0'+bcnt;
            }
        }
    }

    for (int i=1; i<h+1; i++) {
        for (int j=1; j<w+1; j++) {
            cout << s.at(i).at(j);
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 3532
/** Which of the favors of your Lord will you deny ? **/

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

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define MP make_pair
#define F first
#define S second

#define ALL(x) (x).begin(), (x).end()
#define DBG(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << endl
#define READ        freopen("alu.txt", "r", stdin)
#define WRITE       freopen("vorta.txt", "w", stdout)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class TIn>using indexed_set = tree<TIn, null_type, less<TIn>,rb_tree_tag, tree_order_statistics_node_update>;

/**

PBDS
-------------------------------------------------
1) insert(value)
2) erase(value)
3) order_of_key(value) // 0 based indexing
4) *find_by_order(position) // 0 based indexing

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int nmax = 1e7+7;
const LL LINF = 1e17;

template <class T>
string to_str(T x)
{
    stringstream ss;
    ss<<x;
    return ss.str();
}

//bool cmp(const PII &A,const PII &B)
//{
//
//}

LL d[nmax];
LL ans[nmax];

void sieve()
{
    LL N = 1e7;

    for(LL i=1;i<=N;i++)
        for(LL j=i;j<=N;j+=i)
            d[j]++;

    for(LL i=1;i<=N;i++)
        ans[i] = i*d[i] , ans[i] += ans[i-1];
}

int main()
{
    optimizeIO();

    sieve();

    LL n;
    cin>>n;

    cout<<ans[n]<<endl;


    return 0;
}

/**

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}




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

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

  if (a + b > c + d) {
    cout << "Left" << endl;
  } else if (a + b == c + d) {
    cout << "Balanced" << endl;
  } else {
    cout << "Right" << endl;
  }
}

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

int main(){
	int n;
	cin >> n;
	while(n--){
		int num[9];
		int cnt=0;
		int card[3][15]={0};
		for(int i=0;i<9;i++){
			cin >> num[i];
		}
		int c;
		for(int i=0;i<9;i++){
			char color; cin >> color;
			if(color == 'R') c = 0;
			else if(color == 'B') c = 1;
			else c = 2;
			card[c][num[i]]++;
		}
		for(int i=0;i<3;i++){
			for(int j=1;j<=9;j++){
				if(card[i][j] >= 3) {
					card[i][j] -= 3;
					cnt++;
				}
				while(card[i][j]>0 && card[i][j+1]>0 && card[i][j+2]>0){
					card[i][j]--; card[i][j+1]--; card[i][j+2]--;
					cnt++;
				}
			}
		}
		if(cnt==3) cout << "1" << endl;
		else cout << "0" << endl;
	}
}

Measured memory_bytes: 1156
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <queue>
#include <tuple>
#include <cstring>

#define INF 100000000

using namespace std;

int main()
{
    char a;
    cin >> a;
    if (a == 'a' || a == 'i' || a == 'u' || a == 'e' || a == 'o')
        cout << "vowel\n";
    else
        cout << "consonant\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(void){
  string s;
  int cnt = 0;
  cin >> s;
  for(int i = 0; i < s.size(); i++){
    if(s[i] == '1') cnt++;
  }
  cout << cnt << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define fi first
#define se second
#define For(i,a,b) for(ll i=a;i<b;i++)
#define sz size()
#define PQ priority_queue
#define len length()
#define mll map<ll,ll>
#define vll vector<ll>
#define vpll vector<pair<ll,ll> >
#define mp(x,y)  make_pair(x,y)
#define pb push_back
#define pf push_front
#define ALL(v) v.begin(),v.end()
#define LAPAK ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

const ll MOD = 1000000007;

int main() {
	ll n,w;
	cin>>n>>w;
	ll val[n],wt[n];
	ll dp[w+1]={0},maxi=0;
	For(i,0,n){
	    cin>>wt[i]>>val[i];
	    
	    for(ll j=w;j>=0;j--){
	        if(dp[j]!=0){
    	        ll total_weight = wt[i]+j;
    	        if(total_weight<=w){
    	            dp[total_weight]=max(dp[j]+val[i],dp[total_weight]);
    	        }
	        }
	    }
	    dp[wt[i]]=max(val[i],dp[wt[i]]);
	}
	For(i,0,w+1){
	    maxi=max(maxi,dp[i]);
	}
	cout<<maxi;
	return 0;
}

/*            *          *******        *       *    *
             * *            *          * *       *  *
coded by    *****           *         *****        *
           *     *      *   *        *     *       *
          *       *      * *        *       *      *
*/


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin>>n;
  if(n/100==7){
    cout<<"Yes"<<endl;
  }else if((n/10)%10==7){
    cout<<"Yes"<<endl;
  }else if(n%10==7){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

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

int main() {
	char x,y;
	scanf("%c %c", &x, &y);
	if (x < y) {
		printf("<");
	}
	else if (x == y) {
		printf("=");
	}
	else {
		printf(">");
	}
	return 0;
}

Measured memory_bytes: 128
from bisect import bisect_right
import sys
input=sys.stdin.readline
 
 
class LazySegTree():
    def __init__(self, N):
        self.INF = 2**31-1
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)
 
    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
 
        m = []
        for i in range(self.LV):
            if rc <= i:
                m.append(R)
            if L < R and lc <= i:
                m.append(L)
            L >>= 1; R >>= 1
        
        return m
    
    # 遅延伝搬処理
    def propagates(self, ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0
 
    # 区間[l, r)にxを加算
    def update(self, l, r, x):
        ids = self.gindex(l, r)
        self.propagates(ids)
 
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])
    
    # 区間[l, r)内の最小値を求める
    def query(self, l, r):
        self.propagates(self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r
 
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
 
    def set_list(self, l, N):
        for i in range(N):
            self.data[i+self.N0-1] = l[i]
        for i in range(self.N0-1)[::-1]:
            self.data[i] = max(self.data[2*i+1], self.data[2*i+2])


def solve():
    N, D, A = map(int, input().split())
    l = [list(map(int, input().split())) for _ in range(N)]

    l.sort()
    lh = [h for x,h in l]
    lx = [x for x,h in l]
    tree = LazySegTree(N)
    tree.set_list(lh, N)
    ans = 0

    for i in range(N):
        v = tree.query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            pos = bisect_right(lx, lx[i]+2*D)
            tree.update(i, pos, -c*A)
            ans += c

    print(ans)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 112872
var
a,b,c,i:longint;
function aa:string;
begin
for i:=1 to 1000 do
if i*i=c then exit('Yes');
exit('No');
end;
begin

read(a,b);
if b<10 then c:=a*10+b else
if b<100 then c:=a*100+b else
if b=100 then c:=a*1000+b;

writeln(aa);
end.

Measured memory_bytes: 128
#include <iostream>

using namespace std;
using ll = long long;
using ld = long double;

#define ALL(x) begin(x), end(x)
#define REP(i, n) for (size_t i = 0, i##_len = (n); i < i##_len; ++i)

void solve(ll N) {
  string ABC = "ABC";
  cout << ABC + to_string(N) << endl;
}

int main() {
  ll N;
  cin >> N;
  solve(N);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
int n,m;
int a[100010];
map<int, int> mp;
int main()
{
	ll sum=0;
	scanf("%d",&n);
	for (int i=0;i<n;i++) scanf("%d",&a[i]),mp[a[i]]++,sum+=a[i];
	scanf("%d",&m);
	while (m--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		sum+=(ll)mp[x]*(y-x);
		mp[y]+=mp[x],mp[x]=0;
		printf("%lld\n",sum);
	}
	return 0;
}

Measured memory_bytes: 8456
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int l = 0;
        int r = a[0]+1;
        while(1 < r - l ){
            int m = (l + r) /2;
            int tmp = m;
            boolean over = false;
            boolean odd = false;
            for (int i = 0; i < n; i++) {
                if(a[i] < tmp){
                    if(i % 2 != 0) odd = true;
                    over = true;
                    break;
                }
                tmp = a[i] - tmp;
            }
            if((over&&odd) || (!over && m <= tmp)) l = m;
            else r = m;
        }
        int[] ans = new int[n];
        ans[0] = l;
        StringBuilder sb = new StringBuilder();
        sb.append(ans[0] * 2).append(" ");
        for (int i = 1; i < n; i++) {
            ans[i] = a[i-1] - ans[i-1];
            sb.append(ans[i] * 2).append(" ");
        }
        System.out.println(sb.toString());
        sc.close();

    }

}


Measured memory_bytes: 55136
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int x = sc.nextInt();
    int y = sc.nextInt();

    System.out.println(Math.min(n, k) * x + Math.max(n - k, 0) * y);

  }
}

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

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int main() {
	int n, maxed = 1;
	cin >> n;
	
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	
	vector<pair<int, int>> range(n, { 1, 1 });
	range[1].first = a[0];
	for (int i = 2; i < n; i++) {
		range[i].first = gcd(range[i - 1].first, a[i - 1]);
	}
	
	range[n - 2].second = a[n - 1];
	for (int i = n - 3; i >= 0; i--) {
		range[i].second = gcd(range[i + 1].second, a[i + 1]);
	}
	
	range[0].first = range[0].second;
	range[n - 1].second = range[n - 1].first;
	
	for (int i = 0; i < n; i++) {
		if (gcd(range[i].first, range[i].second) > maxed) maxed = gcd(range[i].first, range[i].second);
	}
	
	cout << maxed;
	
	return 0;
}

Measured memory_bytes: 1408