akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define en '\n'
#define fs first
#define sd second

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    n = n%10;
    if(n == 3){
        cout << "bon" << en;
    }else if(n == 0 or n == 1 or n == 6 or n == 8){
        cout << "pon" << en;
    }else{
        cout << "hon" << en;
    }
}

Measured memory_bytes: 3648
#include "bits/stdc++.h"
using namespace std;
#define INF 1e9
#define rep(i, n) for(int i=0;i<n;i++)
#define ALL(x) (x).begin(), (x).end()  //昇順
#define RALL(x) (x).rbegin(), (x).rend() // 降順
const long long mod = 1e9+7;
typedef long long ll;  //ll とdoubleは違う
typedef priority_queue<int> PQ;
typedef vector<long long> VL;
typedef vector<bool> VB;
typedef vector<int> VI;  // VI a(n);
typedef vector<double> VD;  
typedef vector<string> VS;  
typedef vector<char> VC; 
typedef vector<VS> VSS;
typedef vector<VC> VCC;    
typedef vector<VI> VII;   // VII a(n,vector<int>(m)) n * m 
typedef vector<VL> VLL;
typedef pair<int, int> PII;
typedef map<int, int> MP;   //MP a;
typedef vector<pair<ll, ll> > PS;
void input() {}
template<typename... R> void input(int& f, R&... r) { scanf("%d", &f); input(r...); }
template<typename... R> void input(double& f, R&... r) { scanf("%lf", &f); input(r...); }
template<typename... R> void input(ll& f, R&... r) { scanf("%lld", &f); input(r...); }
template<typename... R> void input(char& f, R&... r) { scanf("%c", &f); input(r...); }
template<typename T, typename... R> void input(vector<T>& f, R&... r) { rep(i, f.size())input(f[i]); input(r...); }

template <class T, class U>  // chmax(max, a);
bool chmax(T &a, U b){
    if (a < b){ a = b;return 1;}
    return 0;
}
template <class T, class U> //chmin(min,a)
bool chmin(T &a, U b){
    if (a > b){ a = b; return 1;}
    return 0;
}
template<typename T>   // operator << (cout,a);
ostream& operator << (ostream& os, vector<T>& v) {
    os << "{";
    rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
    os << "}";
    return os;
}
// g++ -std=c++11 prac.cpp 

int main(){
    ll x=0,y=0,z=0,n,m=0,k,h,w,sum=0,Max=-1e9-1,count=0,Min=1e9+1;
    string s,t,u;
    bool ok=true;
    cin >> n >> s >> t;
    while(n>0){
        u += s[x];
        u += t[x];
        s.erase(0);
        t.erase(0);
        n--;
        x++;
    }
   
    cout << u << endl;
    return 0;
}


Measured memory_bytes: 256
/*            AUTHOR - SHIVAM GUPTA
                       Jalpaiguri Govt. Engg College             */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
vector<ll> ve[100005];
ll vis[100005],z;

void solve()
{
    ll n=0,m=0,i=0,j=0,k=0,c=0,l=0,r=0,p=0,q=0,x=0,y=0,z=0,flag=0,sum=0;
    ll a[105]={0},b[100005]={0};
    cin>>n>>k;
    for(i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    for(i=k;i>(k-a[0]);i--)
    b[i]=1;
    for(i=k;i>0;i--)
    {
        for(j=0;j<n;j++)
            if(i-a[j]>=0){
                if(b[i]==1)
                    b[i-a[j]] = 2;
                else if(b[i]==2){
                    if(b[i-a[j]]!=2)
                        b[i-a[j]] = 1;
                    else
                        b[i-a[j]] = 2;
                }
            }
    }
    for(i=0;i<n;i++)
    {
        if(b[a[i]]==1)
        {
            cout<<"First\n";
            return;
        }
    }
    cout<<"Second\n";
}
bool imp=false;int main()
{
    fio;
    int t=1;
    if(imp)
	cin>>t;
	ll j=t;
    while(t--){
    // cout<<"Case #"<<j-t<<": ";
    solve();}
    return 0;
}

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

#define INF ((1<<30)-1)
#define LLINF (1LL<<60)
#define EPS (1e-10)

int main() {
    ll A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;

    ll ans = LLINF;
    for (int i = 0; i <= X; ++i) {
        ll tmp = (i * A) + (X - i) * 2LL*C;
        ll tmpY = Y - (X - i);
        if (tmpY > 0) {
            if (B < 2*C) tmp += tmpY * B;
            else tmp += 2*C * tmpY;
        }
        ans = min(ans, tmp);
    }

    cout << ans << endl;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int ui;

int main()
{
    int n; scanf("%d", &n);
    map<int, int> S;
    for(int i=0; i<n; i++)
    {
        int x; scanf("%d", &x);
        S[x] += 1;
    }

    int m; scanf("%d", &m);
    for(int i=0; i<m; i++)
    {
        int x; scanf("%d", &x);
        if(S[x] == 0)
        {
            cout << "NO\n";
            return 0;
        }
        S[x]--;
    }

    cout << "YES\n";

    return 0;
}


Measured memory_bytes: 9600
fun main(arr:Array<String>) {
    val numberCount = readLine()!!.toInt()
    val list = (1..numberCount).map { readLine()!!.toInt() }
    val count = mutableMapOf<Int, Int>()
    list.forEach { if(count.containsKey(it)) {count[it] = count[it]!! + 1} else {count[it] = 1} }
    val ans = count.filter { it.value % 2 != 0 }.size
    println(ans)

}


Measured memory_bytes: 45708
#include<iostream>
#include<vector>
#include<limits>

using namespace std;

int main(){
    int N,C;
    vector<vector<int>> D;
    vector<vector<int>> mod;
    cin >> N >> C;
    D = vector<vector<int>>(C,vector<int>(C));
    mod = vector<vector<int>>(3,vector<int>(C));
    for(int i= 0;i<C;i++){
        for(int j= 0;j<C;j++){
            cin >> D[i][j];
        }
    }    
    for(int i= 0;i<N;i++){
        for(int j= 0;j<N;j++){
            int c;
            cin >> c;
            c -= 1;
            for(int k=0;k<C;k++){
                mod[(i+j)%3][k]+=D[c][k];
            }
        }
    }
    int min = numeric_limits<int>::max();
    vector<int> minx(3);
    for(int i=0;i<C;i++){
        for(int j=0;j<C;j++){
            if(i==j) continue;
            for(int k=0;k<C;k++){
                if(k==i || k == j) continue;
                int val = mod[0][i]+mod[1][j]+mod[2][k];
                if(val<min){
                    min = val;
                    minx[0] = i;
                    minx[1] = j;
                    minx[2] = k;
                }
            }
        }
    }
    // for(int i=0;i<3;i++){
    //     cout << minx[i] << " ";
    // }
    // cout << endl;
    // for(int i=0;i<3;i++){
    //     for(int j=0;j<C;j++){
    //         cout << mod[i][j] << " ";
    //     }
    //     cout <<endl;
    // }
    cout << min << endl;
    return 0;
}

Measured memory_bytes: 256
import sys


def solve(inp):
    S = inp.readline().rstrip()

    P = ['dream', 'dreamer', 'erase', 'eraser']

    S = ''.join(reversed(S))

    while len(S) > 0:
        f = 0
        for p in P:
            p_str = ''.join(reversed(p))
            if S.startswith(p_str):
                f = 1
                S = S[len(p):]
                break
        if f == 0:
            return "NO"

    return "YES"


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3956
using System; 

namespace Project
{
    class Mains
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            int K = int.Parse(Console.ReadLine());
            char n = S[K-1];

            char[] ca = S.ToCharArray();
            for (int i = 0; i < ca.Length; i++)
            {
                if (ca[i] != n)
                {
                    ca[i] = '*';
                }
            }

            Console.Write(new String(ca));
        }
    }
}


Measured memory_bytes: 11092
#include<stdio.h>

int main(void)
{
	int n,i,g;
	int a[100];	
	scanf("%d",&n);
	for(i = 0;i < n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i = 0;i < n / 2;i++)
	{
		g = a[i];
		a[i] = a[n-1-i];
		a[n-1-i] = g;
	}
	for(i = 0;i < n;i++)
	{
		if(i != (n-1))
			printf("%d ",a[i]);
		else
			printf("%d\n",a[i]);
	}
	return 0;
}

Measured memory_bytes: 596
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 23 15:50:08 2020

@author: liang
"""

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

for a in A:
    d[a-1] += 1
    
d.sort(reverse=True)

ans = N - sum(d[:K])

print(ans)

Measured memory_bytes: 33316
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 200010
using namespace std;
struct node{
	char s[12];
}q[maxn];
char pre[12];
int cmp(node a,node b){
	return strcmp(a.s,b.s)<0;
}
int main(){
	int n,i,cnt=1;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%s",q[i].s);
	sort(q+1,q+1+n,cmp);
	strcpy(pre,q[1].s);
	for(i=2;i<=n;i++)
		if(strcmp(q[i].s,pre)!=0)strcpy(pre,q[i].s),cnt++;
	printf("%d\n",cnt);
	return 0;
}


Measured memory_bytes: 4048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	vector<ll>ch;
	for(ll i=0;i<n;i++){
		ll now;
		cin>>now;
		ch.push_back(now);
	}
	sort(ch.begin(),ch.end());
	ll l=ch[n/2-1];
	ll r=ch[n/2];
	cout << r-l;
	// your code goes here
	return 0;
}

Measured memory_bytes: 4248
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

typedef long long ll;

int main(){
  int n, k; cin >> n >> k;
  int a[n];
  vector<int> cnt;
  for(int i=0;i<=200000;i++) cnt.push_back(0);
  for(int i=0;i<n;i++){
    cin >> a[i];
    cnt[a[i]]++;
  }
  sort(cnt.begin(), cnt.end(), greater<int>());
  int sum=0;
  for(int i=0;i<k;i++){
    sum = sum+cnt[i];
  }
  cout << n-sum << endl;
}

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

int main() {
  int y, m, d;
  scanf("%d/%d/%d", &y, &m, &d);
  long ymd = y * 10000 + m * 100 + d;

  printf("%s\n", ymd <= 20190440 ? "Heisei" : "TBD");
  return 0;
}


Measured memory_bytes: 888
#

import sys
input=sys.stdin.readline

def main():
    A,B,C=map(int,input().split())
    K=int(input())
    for i in range(K):
        if A>=B:
            B*=2
        elif B>=C:
            C*=2
    if A<B<C:
        print("Yes")
    else:
        print("No")
    
    
    
if __name__=="__main__":
    main()


Measured memory_bytes: 9172
from collections import Counter
N = int(input())
D = {chr(x+97):100 for x in range(26)}
for i in range(N):
    C = Counter(input())
    for j in range(26):
        x = chr(j+97)
        D[x] = min(D[x],C[x])
Ans = ""
for i in range(26):
    x = chr(i+97)
    Ans += x*D[x]
print(Ans)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define UM unordered_map
#define ALL(a) (a).begin(),(a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 60);
typedef pair<ll,ll> pii;

int main(){
  ll N,V; cin>>N>>V;
  vvi v(4,vi(N));
  REP(i,4) REP(j,N) cin>>v[i][j];
  UM<ll,ll> ab,cd;
  REP(i,N) REP(j,N) ab[v[0][i]+v[1][j]]+=1;
  REP(i,N) REP(j,N) cd[v[2][i]+v[3][j]]+=1;
  ll ans=0;
  for(pii p:ab){
    ans+=p.second*cd[V-p.first];
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 121576
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using u32 = uint32_t;
using vi = vector<int>;    using vvi = vector<vi>;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;

#define MAXC(c, x) (c = max(c, x))
#define MINC(c, x) (c = min(c, x))

#define REP(i,n) for(auto i = 0 * (n), i##_len = (n); i < i##_len; ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,n) for(ll i=s, i##_len=(ll)(n); i<i##_len; ++i)
#define TEN(x) ((ll)1e##x)
const ll mod = TEN(9) + 7;

const ll INF = 1e9;

int main() {
	#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
	#endif
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);

	ll k, n; cin >> k >> n;

	if (k % 2 == 0) {
		cout << k / 2;
		REP(i, n - 1) cout << " " << k;
		cout << endl;
		return 0;
	}

	////////////////////////////////////////////

	const ll mid = k / 2 + k % 2;

	vl ans(n);
	REP(i, n) ans[i] = mid;

	ll idx = n - 1;
	vl cur(n); cur[n - 1] = mid + 1;
	vl sum(n + 1); sum[n - 1] = k + 1; sum[n] = 1;
	while (cur[idx] <= n - 1) {
		cur[idx - 1] = cur[idx] + (mid - 1) * sum[idx] + 1;
		sum[idx - 1] = k * sum[idx] + 1;
		idx--;
	}

	ll x = n - 1;
	x = cur[idx] - (x / 2 + x % 2);
	while (x) {
		x--;
		if (x == 0) break;

		ans[idx] = x / sum[idx + 1] + (x % sum[idx + 1] != 0);
		x -= x / sum[idx + 1] * sum[idx + 1];
		idx++;
	}

	REP(i, idx - 1) cout << ans[i] << " ";
	cout << ans[idx - 1] << endl;

	return 0;
}


Measured memory_bytes: 9344
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
const int INF=1e9;
using namespace std;

int main(){
    int a, b, c, x;
    cin>>a>>b>>c>>x;
    int sum=0, ans=0;
    for(int i=0; i<=a; i++){
        for(int j=0; j<=b; j++){
            for(int k=0; k<=c; k++){
                sum=i*500+j*100+k*50;
                if(sum==x)ans++;
                sum=0;
            }
        }
    }
    cout<<ans<<endl;
}


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

using namespace std;

#ifndef errOut
#define errOut(s)
#endif

int calc(const std::string& s) {
  int const n = static_cast<int>(s.length());
  int ret = 0;
  for (int i = 1; i < n - 1; ++i) {
    std::string s1 = s.substr(0, i);
    std::string s2 = s.substr(i);
    int found = 0;
    for (char c = 'a'; c <= 'z'; ++c) {
      if (s1.find(c) == string::npos || s2.find(c) == string::npos) {
        continue;
      }
      ++found;
    }
    ret = std::max(found, ret);
  }
  return ret;
}

int main() {
  int n;
  std::string s;
  std::cin >> n >> s;
  int ret = calc(s);
  std::cout << ret << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void)
{
	int n,l,i,j;
	char str[101][101],tmp[101];
	scanf("%d %d",&n,&l);
	for(i=0;i<n;i++){
		scanf("%s",str[i]);
	}
	for (i=0;i<n;i++) {
		for (j=i+1;j<n;j++) {
			if(strcmp(str[i],str[j])>0) {
				strcpy(tmp,str[i]);
				strcpy(str[i],str[j]);
				strcpy(str[j],tmp);
			}
		}
	}
	for (i=0;i<n;i++) {
	printf("%s",str[i]);
	}
	printf("\n");	
	return 0;
}

Measured memory_bytes: 128
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<ll>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    int n, m;
    cin >> n >> m;
    vi x(n), y(n), z(n);
    rep(i, n) {
        cin >> x[i] >> y[i] >> z[i];
    }

    vi dp;
    int kirei[2] = {1, -1};
    int oisisa[2] = {1, -1};
    int ninkido[2] = {1, -1};
    ll ans = -LINF;
    rep(i, 2) {
        rep(j, 2) {
            rep(k, 2) {
                dp.assign(m+1, -LINF);
                dp[0] = 0;
                rep(q, n) {
                    for(int l = m; l>0; --l) {
                        if(dp[l-1] == -LINF) continue;
                        dp[l] = max(dp[l], dp[l-1] + x[q]*kirei[i] + y[q]*oisisa[j] + z[q]*ninkido[k]); 
                    }
                }
                ans = max(ans, dp[m]);
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
# import bisect
# from collections import Counter, defaultdict, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, k = list(map(int,ipti().split()))
    print(n-k+1)

if __name__ == '__main__':
    main()

Measured memory_bytes: 38256
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=100000+10;
int S[MAXN],n,x,ans;
inline void read(int &x)
{
	int data=0,w=1;
	char ch=0;
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch>='0'&&ch<='9')data=(data<<3)+(data<<1)+(ch^'0'),ch=getchar();
	x=data*w;
}
int main()
{
	read(n);
	for(register int i=1;i<=n;++i)
	{
		read(x);
		S[x]++;
		S[x-1]++;
		S[x+1]++;
		ans=max(ans,S[x]);
		ans=max(ans,S[x+1]);
		ans=max(ans,S[x-1]);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
sosu=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
n=int(input())
ans=1
p=10**9+7
for i in sosu:
  if i<=n:
    stack=0
    num=i
    while num<=n:
      stack+=n//num
      num*=i
    ans*=(stack+1)
    ans%=p
print(ans)

Measured memory_bytes: 3188
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Main p = new Main();
	}
	
	public Main(){
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		int n = sc.nextInt();
		char[][] field = new char[w+2][h+2];
		Point start = null;
		for(int i=1;i<=h;i++){
			String line = sc.next();
			for(int j=1;j<=w;j++){
				field[j][i] = line.charAt(j-1);
				if(field[j][i] == 'S')
					start = new Point(j,i);
			}
		}
		for(int i=0;i<w+2;i++){
			field[i][0] = 'X';
			field[i][h+1] = 'X';
		}
		for(int i=0;i<h+2;i++){
			field[0][i] = 'X';
			field[w+1][i] = 'X';
		}
		
		
		solve(h, w, field, n, start);
	}
	


	private void solve(int h, int w, char[][] field, int n, Point start){
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		int[][] d = new int[w+2][h+2];
		LinkedList<Point> queue = new LinkedList<Point>(); 
		
		int res = 0;
		final int INF = Integer.MAX_VALUE;
		for(int i=1;i<=n;i++){
			for(int j=0;j<d.length;j++)
				Arrays.fill(d[j], INF);
			queue.offer(start);
			d[start.x][start.y] = 0;
			
			while(!queue.isEmpty()){
				Point p = queue.poll();

				for(int j=0;j<4;j++){
					int nx = p.x+dx[j];
					int ny = p.y+dy[j];
					if(field[nx][ny]!='X' && d[nx][ny] == INF){
						if(field[nx][ny]==i+'0'){
							queue.clear();
							start = new Point(nx, ny);
							res += d[p.x][p.y]+1;
							break;
						}else{
							d[nx][ny] = d[p.x][p.y]+1;
							queue.offer(new Point(nx, ny));
						}
					}
				}
			}
		}
		
		
		System.out.println(res);
	}
	
	private class Point{
		int x;
		int y;
		
		public Point(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
}

Measured memory_bytes: 93856
import sys
from itertools import combinations_with_replacement


def main():
    input = sys.stdin.buffer.readline
    n, m, q = map(int, input().split())
    query = [list(map(int, input().split())) for _ in range(q)]
    li = [i for i in range(1, m + 1)]
    max_point = 0
    for a in combinations_with_replacement(li, n):
        point = 0
        for qer in query:
            if a[qer[1] - 1] - a[qer[0] - 1] == qer[2]:
                point += qer[3]
        if point > max_point:
            max_point = point
    print(max_point)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9168
N = int(input())
A, B = [None]*N, [None]*N

time = 0
for i in range(N):
    A[i], B[i]= map(int, input().split())
    if A[i] > B[i]:
        print('No')
        quit()

index = sorted(range(N), key=lambda k: B[k])
for ind in index:
    if time + A[ind] > B[ind]:
        print('No')
        quit()
    else:
        time += A[ind]
print('Yes')

Measured memory_bytes: 28592
import itertools

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))


answer = list(range(1, N + 1))


def solve(temp):
    index = 0
    for group in itertools.permutations(answer, N):
        if list(group) == temp:
            return index
        index += 1


answer = solve(P) - solve(Q)

print(max(answer, -answer))


Measured memory_bytes: 3060
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

class Program
{
	static void Main(string[] args)
	{
		while (true)
		{
			string[] input = Console.ReadLine().Split(' ');
			int range = int.Parse(input[0]);
			int sum = int.Parse(input[1]);
			int cnt = 0;

			if (range == 0 && sum == 0) break;

			for (int i = 1; i < (range - 1); i++)
			{
				for (int j = (i + 1); j < range; j++)
				{
					for (int k = (j + 1); k < range +1; k++)
					{
						int value = i + j + k;
						if (value == sum)
							cnt += 1;
					}
				}
			}
			Console.WriteLine(cnt);
		}

		return;
		//Console.WriteLine("");

	}
}

Measured memory_bytes: 9116
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
int main(void){
  int N;
  cin>>N;
  int W[N];
  int sum=0;
  rep(i,N){
      cin>>W[i];
      sum+=W[i];
  }
  int T=0;
  int m=1000000;
  rep(i,N){
      T+=W[i];
      sum-=W[i];
      m=min(m,abs(T-sum));
  }
  
  cout<<m<<endl;
  
}

Measured memory_bytes: 3548
#include<bits/stdc++.h>
using namespace std;
int n;
int dp[2][3];
int main(){
	scanf("%d",&n);
	while(n--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		memset(dp[n&1],-1,sizeof(dp[n&1]));
		dp[n&1][0]=max(dp[~n&1][1],dp[~n&1][2])+a;
		dp[n&1][1]=max(dp[~n&1][0],dp[~n&1][2])+b;
		dp[n&1][2]=max(dp[~n&1][0],dp[~n&1][1])+c;
	}
	printf("%d\n",max(dp[0][0],max(dp[0][1],dp[0][2])));
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

#define N_MAX 100010

void solv()
{
	int N, M; scanf("%d%d", &N, &M);
	char S[N_MAX]; scanf("%s", S);
	char revS[N_MAX];
	for (int i = 0; i <= N; i++){
		revS[i] = S[N - i];
	}

	int turn = 0, cur = 0;
	vector<int> ret;
	while (true){
		bool impossible = true;
		for (int i = min(N, cur + M); i > cur; i--){
			if ('0' == revS[i]){
				ret.push_back(i - cur);
				cur = i;
				turn++;
				impossible = false;
				break;
			}
		}
		if (impossible){
			printf("-1");
			return;
		}
		if (N == cur){
			break;
		}
	}

	for (int i = 0; i < turn; i++){
		printf("%d ", ret[turn - i - 1]);
	}

	return;
}

int main()
{
	FILE *fin = NULL, *fout = NULL;
	//fin = freopen("input.txt", "r", stdin);
	//fout = freopen("output.txt", "w", stdout);

	solv();

	//finalize
	if (NULL != fin) fclose(fin);
	if (NULL != fout) fclose(fout);

	return 0;
}

Measured memory_bytes: 1144
MOD = 10**9 + 7

def power_mod(a,n):
    if n == 0:
        return 1
    x = (power_mod(a,n//2)**2)%MOD
    return x if n%2 == 0 else (a*x)%MOD

def inverse(a):
    return power_mod(a,MOD-2)

def comb(n,k):
    # k is small
    num = 1
    den = 1
    for i in range(1,k+1):
        num *= (n+1-i)
        den *= i
        num %= MOD
        den %= MOD
    return (num * inverse(den))%MOD

def solve(N,M,min_p=2):
    if M == 1:
        return 1
    for p in range(min_p, M+1):
        if p*p > M:
            # M is prime
            return N
        if M%p != 0:
            continue
        e = 0
        while M%p == 0:
            M //= p
            e += 1
        return (solve(N, M, p) * comb(N-1+e,e))%MOD
      
N,M = map(int, input().split())
ans = solve(N,M)

print(ans)

Measured memory_bytes: 3064
$<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |given|
  ls = given.first(10)
  v1, v2 = given[10, 2]
  s = Rational(v1 * ls.sum, v1 + v2)
  l = 0
  ls.each_with_index do |ln, i|
    l += ln
    next if s > l
    puts i + 1
    break
  end
end


Measured memory_bytes: 6872
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static public void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] nums = new int[N][N];
        boolean[][] exist = new boolean[N][N];
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                nums[i][j] = Math.min(i, Math.min(N-1-i, Math.min(j, N-1-j)));
                exist[i][j] = true;
            }
        }
        long ans = 0;
        for(int i = 0 ; i < N*N ; i++){

            int num = sc.nextInt()-1;
            int x = getColumn(N, num);
            int y = getRow(N, num);
            
            exist[x][y] = false;
            ans += nums[x][y];
            LinkedList<Integer> stack = new LinkedList<Integer>();
            stack.addFirst(getIndex(N, x, y));
            while(!stack.isEmpty()){
                int now = stack.removeFirst();
                int nowX = getColumn(N, now);
                int nowY = getRow(N, now);
                int value = nums[nowX][nowY];
                if(exist[nowX][nowY]){
                    value++;
                }
                if(nowX > 0){
                    if(nums[nowX-1][nowY] > value){
                        nums[nowX-1][nowY] = value;
                        stack.addLast(getIndex(N, nowX-1, nowY));
                    }
                }
                if(nowX < N-1){
                    if(nums[nowX+1][nowY] > value){
                        nums[nowX+1][nowY] = value;
                        stack.addLast(getIndex(N, nowX+1, nowY));
                    }
                }
                if(nowY > 0){
                    if(nums[nowX][nowY-1] > value){
                        nums[nowX][nowY-1] = value;
                        stack.addLast(getIndex(N, nowX, nowY-1));
                    }
                }
                if(nowY < N-1){
                    if(nums[nowX][nowY+1] > value){
                        nums[nowX][nowY+1] = value;
                        stack.addLast(getIndex(N, nowX, nowY+1));
                    }
                }
            }
        }
        System.out.println(ans);
    }

    static int getColumn(int N, int v){
        return v%N;
    }

    static int getRow(int N, int v){
        return v/N;
    }

    static int getIndex(int N, int column, int row){
        return N*row + column;
    }
}


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

int main(){
   int A, B, H, M;
   cin >> A >> B >> H >> M;
   double hs, ms;
   hs = 0.5 * (H*60+M);
   ms = 6 * M;
   double sita = abs(hs - ms);
   if (sita > 180){
      sita = 360 - sita;
   }
   //cout << "hs; " << hs << " " << "ms: " << ms << " " << "sita: " << sita << endl;
   double rsita;
   rsita = 3.1415926535897932384626433 * sita / 180;
   double c2;
   c2 = pow(A, 2) + pow(B, 2) - 2 * A * B * cos(rsita);
   double c;
   c = sqrt(c2);
   cout << setprecision(20) << c << endl;
}



Measured memory_bytes: 4132
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

k = ni()
que = deque([(1,1)])

kmod = [0]*k

while kmod[0] == 0:
    cost, idx = que.popleft()
    if kmod[idx] == 0:
        kmod[idx] = cost
        que.appendleft((cost, (10*idx%k)))
        que.append((cost+1, (idx+1)%k))            
        
print(kmod[0])

Measured memory_bytes: 43504
n = int(input())
x = []
y = []
for i in range(n):
    tmp_x, tmp_y = list(map(int, input().split()))
    x.append(tmp_x + tmp_y)
    y.append(tmp_x - tmp_y)
    
max_x = max(x) - min(x)
max_y = max(y) - min(y)
print(max(max_x, max_y))

Measured memory_bytes: 24948
import heapq
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())

event_list=[]
for i in range(N):
  S,T,X=map(int,input().split())
  event_list.append((S-X-0.5,1,X))
  event_list.append((T-X-0.5,-1,X))
  
dlist=[]
for i in range(Q):
  D=int(input())
  event_list.append((D,0,X))  
  dlist.append(D)
event_list.sort()
#print(event_list)

answer_dic={}
stop_set=set()
hq=[]
for t,f,x in event_list:
  if f==1:
    stop_set.add(x)
    heapq.heappush(hq,x)
  elif f==-1:
    stop_set.remove(x)
  else:
    if len(stop_set)>0:
      while(True):
        if hq[0] in stop_set:
          answer_dic[t]=hq[0]
          break
        else:
          heapq.heappop(hq)
    else:
      answer_dic[t]=-1
#print(answer_dic)

for d in dlist:
  print(answer_dic[d])

Measured memory_bytes: 108724
from collections import defaultdict, deque
    
N, Q = map(int, input().split())

edge = defaultdict(set)
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a].add(b)
    edge[b].add(a)

score = [0]*(N+1)
for j in range(Q):
    p, x = map(int, input().split())
    score[p]+=x
    
q = deque()
q.append(1)
visited = [0]*(N+1)
while q:
    v = q.pop()
    visited[v]=1
    for u in edge[v]:
        if visited[u]:
            continue
        else:
            score[u]+=score[v]
            q.append(u)

for i in range(1, N+1):
    print(score[i], end=' ')

Measured memory_bytes: 123828
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var x = int.Parse(Console.ReadLine());
            var result = 0;
            if (x >= 500)
            {
                var c = x / 500;
                result += 1000 * c;
                x -= c * 500;
            }
            if (x >= 5)
            {
                var c = x / 5;
                result += 5 * c;
            }

            Console.WriteLine(result);
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

// retun n の約数の集合
vector<ll> yakusuu(ll n){
      vector<ll> y;
    for(ll i = 1; i * i <= n; i++){
        if(n % i == 0) y.push_back(i);
    }
      ll len = y.size();
      REP(i, len){
        if(y[i] == n / y[i]) continue;
        y.push_back(n / y[i]);
    }
    return y;
}

const ll inf = 1e18;

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

    ll n;
    cin >> n;

    ll res = inf;
    vll y = yakusuu(n);

    for (auto x : y) {
        ll z = n / x;
        ll tmp = x + z - 2;
        res = min(res, tmp);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 384
from collections import deque
N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1;b-=1;G[a].add(b);G[b].add(a)
q=deque([]);q.append(0)
used=[0 for i in range(N)];used[0]=1
while(True):
    flag=0
    a=q[0]
    for p in G[a]:
        if used[p]==0:
            q.appendleft(p)
            used[p]=1
            flag=1
            break
    b=q[-1]
    for p in G[b]:
        if used[p]==0:
            q.append(p)
            used[p]=1
            flag=1
            break
    if flag==0:
        break
ans=[str(i+1) for i in q]
print(len(ans))
print(" ".join(ans))

Measured memory_bytes: 41172
import sys
input = sys.stdin.readline

from collections import Counter
from itertools import accumulate
from math import floor
from bisect import bisect_left


def main():
    n = int(input())
    a = list(map(int, input().split()))

    c = Counter(a)
    c = list(c.values())

    d = Counter(c)
    d_li = [0] * (n + 1)
    for k, v in d.items():
        d_li[k] = v

    dk_acm = list(accumulate(d_li))

    kdk_acm = [0]
    for k, e in enumerate(d_li[1:], 1):
        kdk_acm.append(kdk_acm[-1] + k * e)

    def f(x):
        kdk_sm = kdk_acm[x]
        dk_sm = dk_acm[n] - dk_acm[x]

        return floor((kdk_sm + x * dk_sm) / x)

    fs = [float("inf")] + [f(x) for x in range(1, n + 1)]
    fs = fs[::-1]

    for k in range(1, n + 1):
        print(n - bisect_left(fs, k))


if __name__ == "__main__":
    main()


Measured memory_bytes: 59860
#include<iostream>

using namespace std;

int main() {
	int n;
	int a,b,c;
	cin >> n;
	for(int i=0;i<n;i++){
		std::string p = "NO";
		cin >> a >> b >> c;
		if (a>b && a>c && a*a==b*b+c*c){p = "YES";}
		if (b>a && b>c && b*b==a*a+c*c){p = "YES";}
		if (c>a && c>b && c*c==a*a+b*b){p = "YES";}
		cout << p << endl;
	}


	return 0;
}



Measured memory_bytes: 3148
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i, a, n) for(int i=a; i<n; i++)
#define ll long long
#define all(x) begin(x), end(x)
#define toInt(x) (x - '0')
#define pll pair<ll, ll>
#define pli pair<ll, int>

const long long INF = 1LL<<60;
const int inf = 1 << 30;
const int mod = 1e9+7;


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


int main(){
  long long n, k;
  cin >> n >> k;
  vector<long long> a(n);

  rep(i, 0, n){
    int c;
    cin >> c;
    c--;
    a[i] = c;
  }

  vector<bool> used(n, false);
  int curr = 0;
  int cnt = 1;
  int s=-1;
  used[0] = true;
  for (int i=0; i<n; i++){
    if(used[a[curr]]){
      s = a[curr];
      break;
    }
    used[a[curr]] = true;
    curr = a[curr];
    cnt++;
  }
  int step;
  //閉路検出
  if(s!= -1){

  long long till_s=0;
  int curr =0;
  for(int i=0; i<n; i++){
    if(curr == s){
      break;
    }
    curr = a[curr];
    till_s++;
  }

  // cout << till_s << endl;
    step = min(till_s, k) + (k - min(till_s, k)) % (cnt-till_s);
  }else{
    step = k % n;
  }

  int cirr = 0;
  for(int i=0; i<step; i++){
    cirr = a[cirr];
  }
  cout << cirr+1 << endl;
}

Measured memory_bytes: 4844
arr = (1..26).select{|i| 26.gcd(i)==1}
c = ('a'..'z').to_a
gets.to_i.times do
  s = gets
  hints = s.split.select{|i| i.size==4}
  @alpha = arr.find do |a|
    @beta = (0..26).find do |b|
      ["this", "that"].any?{|h|
        hints.include?(h.chars.map{|i| c[(a*c.index(i)+b)%26]}.join)
      }
    end
  end
  map = (0..25).map{|i| (@alpha*i+@beta)%26}
  puts s.chars.map{|i| c.include?(i) ? c[map.index(c.index(i))] : i }.join
end

Measured memory_bytes: 6148
s = str(input())
ans = []
for i in range(len(s)):
    if s[i] == 'A':
        ans += '1'
    elif s[i] == 'C':
        ans += '1'
    elif s[i] == 'G':
        ans += '1'
    elif s[i] == 'T':
        ans += '1'
    else:
        ans += '0'

m = ''.join(ans)
m2 = m.split('0')
mx = max(m2)
print(len(mx))

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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const ll mod = 1e9+7;

void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int main()
{
 
	//cin.tie(0); ios_base::sync_with_stdio(false);
	string s;
	cin >>s;
	int n=sz(s), ans =sz(s);
	s = "0"+s+"0";
	VI ck(n+2);
	rep(i, n+1) if(s[i] != s[i+1]) ck[i]=1;
	
	rep(i, n+1) if(ck[i]==1) ans = min(ans, max(i, n-i));
	cout << ans <<"\n";
	return 0;
}


Measured memory_bytes: 892
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define ALL(obj) (obj).begin(),(obj).end()
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef priority_queue<int> p_que;
typedef priority_queue<int, vector<int>, greater<int>()> p_que_rev;
// const int INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};


int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    lint k;
    cin >> k;
    const lint n = 50;
    vector<lint> a(n);
    for (int i=0; i<n; ++i){
        a[i] = i;
    }
    lint p = k / n;
    lint r = k % n;
    if(r == 0){
        for (int i=0; i<n; ++i){
            a[i] = p + i;
        }
    }
    else {
        for (int i=r-1; i>=0; --i){
            a[i] = n + p - (r - 1 - i);
        }
        for (int i=r; i<n; ++i){
            a[i] = i - r + p;
        }
    }
    bool isFst = true;
    cout << n << endl;
    for (int i=0; i<n; ++i){
        if(isFst){
            isFst = false;
            cout << a[i];
        }
        else {
            cout << " " << a[i];
        }
    }
    cout << endl;
    return 0;
}

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

int main() {
  int n, d;
  cin >> n >> d;
  vector<vector<int>> vec(n, vector<int>(d));
  rep(i, n) {
    rep(j, d) {
      cin >> vec.at(i).at(j);
    }
  }
  int count = 0;
  rep(i, n) {
    rep(j, n) {
      int distance = 0;
      rep(k, d) {
        distance += (vec.at(i).at(k)-vec.at(j).at(k))*(vec.at(i).at(k)-vec.at(j).at(k));
      }
      rep(l, 200) {
        if(distance == l*l) count++;
      }
    }
  }
  cout << (count-n)/2 << endl; 
}

Measured memory_bytes: 256
#include <stdio.h>
int solve(int ,int);

int A[20],n;
int main() {
  int i,j,q,m[200],t;
  scanf("%d",&n );
  for (i = 0; i < n; i++) {
    scanf("%d",&A[i] );
  }
  scanf("%d",&q);
  for (i = 0; i < q; i++) {
    scanf("%d",&m[i]);
  }
  for (i = 0; i < q; i++) {
    for (j = 0; j < n; j++) {
  t= solve(j,m[i]);
  if (t ==1) {
    printf("yes\n");
    break;
  }
}
  if (t ==0) {
    printf("no\n");
  }

}
  return 0;
}
int solve(int i,int m){
  int res=0;
   if (m == 0)
   return 1;
   if (i >= n)
  return 0;
  if (solve(i + 1, m - A[i]) == 1 || solve(i + 1, m) == 1)
  res = 1;
  // res = solve(i + 1, m - A[i]);
  return res;
}

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

N, M = map(int, input().split())
E = []
for i in range(M):
    a, b = map(int, input().split())
    E.append((a-1, b-1))

tree = {n: n for n in range(N)}
child = {n: 1 for n in range(N)}

max_connection = N*(N-1)//2


def find_head(i):
    if tree[i] != i:
        tree[i] = find_head(tree[i])
        return tree[i]
    else:
        return i


connection = 0
out_list = [max_connection]
for e in E[:0:-1]:
    head_e0 = find_head(e[0])
    head_e1 = find_head(e[1])

    if head_e0 == head_e1:
        out_list.append(max_connection-connection)
    else:
        tree[head_e1] = head_e0
        connection = connection + child[head_e0]*child[head_e1]
        child[head_e0] += child[head_e1]
        out_list.append(max_connection - connection)
    if max_connection == connection:
        break

if len(out_list) != M:
    out_list += [0]*(M-len(out_list))

for o in out_list[::-1]:
    print(o)


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

#define int long long
using ll = long long;
using ld = long double;
using intpair = pair<int, int>;
using intmap = map<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int MOD = 1e9 + 7;
inline int mod (ll a, int m = MOD) { return (a % m + m) % m; }
inline bool bit (ll b, ll i) { return b & (1 << i); }
inline ll ceiv (ll a, ll b) { return (a + b - 1) / b; }
//struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;

#define debug(x) cerr << #x << ": " << x << '\n'
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()

int binom_max = 5e5+1;
vector<int> fact(binom_max), inv_fact(binom_max), inv(binom_max);

void modbinom_init() {
    fact[0] = fact[1] = 1;
    inv_fact[0] = inv_fact[1] = 1;
    inv[1] = 1;
    for(int i=2; i<binom_max; i++){
        fact[i] = fact[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        inv_fact[i] = inv_fact[i-1] * inv[i] % MOD;
    }
}

int comb(int n, int k){
    if (n<k) return 0;
    if (n<0 || k<0) return 0;
    return fact[n] * (inv_fact[k] * inv_fact[n-k] % MOD) % MOD;
}

int perm(int n, int k){
    if (n<k) return 0;
    if (n<0 || k<0) return 0;
    return (fact[n] * inv_fact[n-k]) % MOD;
}

signed main(){
    modbinom_init();
    int n, k;
    cin >> n >> k;
    int limit = min(k, n-1);
    
    int ans = 0;
    for(int i = 0; i <= limit; i++){
        ans = mod(ans + mod(comb(n-1, i) * comb(n, i)));
    }
    
    cout << ans << endl;
}

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

int main(){
    string s;
    cin >> s;
    string new_s;
    for (int i=0;i<s.size();i++){
        if (i % 2 == 0){
            new_s+=s[i];
        }
    }
    cout << new_s << endl;
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>

#define N 2<<10

using namespace std;

int main(){

  int data[31], num, ac, team[N];
  char trash;
  vector<int> V;

  for(int i = 0; i < 31; i++) data[i] = 0;
  for(int i = 0; i < N; i++) team[i] = 0;

  while(cin >> num >> trash >> ac){
    if(num == 0 && ac == 0) break;

    if(data[ac] == 0) V.push_back(ac);

    data[ac] = 1;
    team[num] = ac;
  }

  sort(V.begin(), V.end());
  reverse(V.begin(), V.end());

  while(cin >> num){

    for(int i = 0; i < V.size(); i++){

      if(V[i] == team[num]) cout << i+1 << endl;

    }
  }
  return 0;
}
    
    

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,n) for (int64_t i=0; i<(n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int n; cin>>n;
    vector<int> p(n);
    rep(i,n) cin>>p[i];
    int q; cin>>q;
    vector<P> pp(q);
    rep(i,q) cin>>pp[i].first>>pp[i].second;
    map<int, int> mp;
    ll ans=0;
    rep(i,n){
        mp[p[i]]++;
        ans+=(ll)p[i];
    }
    rep(i,q){
        if(mp[pp[i].first]==0){
            cout<<ans<<endl;
        }
        else{
            ans+=(pp[i].second-pp[i].first)*mp[pp[i].first];
            mp[pp[i].second]+=mp[pp[i].first];
            mp[pp[i].first]=0;
            cout<<ans<<endl;
        }
    }
}

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


int main(){
	int n,a,sum=0,N;
	cin >> n;
	N = n;
	while (n) {
		a = n % 10;
		sum += a;
		n = n / 10;
	}
	if (N % sum == 0) { cout << "Yes"; }
	else { cout << "No"; }



	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
double round(double r)
{
    return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
}

int num[10];
char str[300000];

int main()
{
    cin>>str;
    int len=strlen(str);
    for(int i=0;i<len;i++)
        num[str[i]-'0']++;
    int sum=0;
    for(int i=1;i<9;i++)
        num[i]%=9;
    for(int i=1;i<9;i++)
        sum+=num[i]*i;
    if(sum%9==0)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pb push_back

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b); i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a-1)
#define trav(x, a) for (auto& x: a)

const int MX  = 3005;
const int MOD = 998244353;
const ll  INF = 1061109567; // 4557430888798830399LL
const ld  EPS = 1e-9;
const ld  PI  = acos(-1);

ll qpow(ll b,ll e) {
    if (!e) return 1LL;
    if (e&1) return ((b%MOD)*(qpow(b,e-1)%MOD))%MOD;
    ll res = qpow(b,e/2)%MOD;
    return (res*res)%MOD;
}

ll inv(ll x) {
    return qpow(x,MOD-2);
}

int arr[MX];
int dp[MX][MX];

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N, S; cin >> N >> S;

    FOR(i,1,N+1) cin >> arr[i];

    ll INV = inv(2);

    dp[0][0] = qpow(2,N);
    FOR(i,1,N+1) {
        F0R(j,S+1) {
            dp[i][j] = dp[i-1][j]%MOD;
            if (j-arr[i] >= 0) {
                dp[i][j] = ((dp[i][j]+(dp[i-1][j-arr[i]]*INV)%MOD)%MOD);
            }
        }
    }

    cout << dp[N][S] << "\n";

}


Measured memory_bytes: 38848