akhauriyash/Code-Regression huggingface dataset:
#pragma comment (linker, "/STACK:256000000")
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 2000000000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define MOD 998244353LL
#define seg_size 262144*2
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long a = 0;a < b;++a)
#define ALL(x) (x).begin(),(x).end()
void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}
unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
#define int ll
vector<pair<int,int>> vertexs[300000];
int ans[300000];
int val = 0;
int dfs(int now, int back, int back_color) {
    int next_color = 0;
    for (auto x : vertexs[now]) {
        if (x.first == back) continue;
        next_color++;
        if (next_color == back_color) next_color++;
        ans[x.second] = next_color;
        val = max(val, next_color);
        dfs(x.first, now, next_color);
    }
    return 0;
}
void solve() {
    int n;
    cin >> n;
    REP(i, n-1) {
        int a, b;
        cin >> a >> b;
        vertexs[a].push_back(make_pair(b, i));
        vertexs[b].push_back(mp(a, i));
    }
    dfs(1, -1,0);
    cout << val << endl;
    REP(i, n-1) {
        cout << ans[i] << endl;
    }
}
#undef int
int main() {
    init();
    solve();
}


Measured memory_bytes: 15232
#include<cstdio>
#include<iostream>
using namespace std;
int n,sum=1e9;
int ans(int x)
{
	int t=0;
	while (x)
	{
		t+=x%10;
		x/=10;
	}
	return t;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<n;i++)
		sum=min(sum,ans(i)+ans(n-i));
		printf("%d",sum);
}

Measured memory_bytes: 256
#ifdef _MSC_VER
#pragma warning(disable : 4996)
#include <intrin.h>
#define __builtin_popcount __popcnt
#endif

#include <limits.h>
#include <math.h>
#include <time.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

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 - 1; i >= n; --i)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v, n) reverse(v, v + n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout << (x) << '\n'
#define pe(x) cout << (x) << " "
#define DEBUG(x) cout << #x << ": " << x << endl
#define lb(v, n) lower_bound(v.begin(), v.end(), (n))
#define ub(v, n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i, v.size()) cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template <typename T1, typename T2> inline void chmin(T1& a, T2 b) {
	if (a > b) a = b;
}
template <typename T1, typename T2> inline void chmax(T1& a, T2 b) {
	if (a < b) a = b;
}
typedef pair<int, int> pii;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7;
constexpr int MAX = 200020;
const double pi = acos(-1);
constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;


void solve() {
	int ans = 1;
	int N; cin >> N;
	REP(i, 10) {
		if ((1 << i) <= N)ans = (1 << i);
	}
	cout << ans << endl;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	// int q; cin >> q;
	// while (q--)
	solve();
}


Measured memory_bytes: 256
N,K=list(map(int,input().split()))

arr=[]
for i in range(N):
    arr.append(int(input()))
arr=sorted(arr)

ans=10**20
for i in range(N-K+1):
    if ans > arr[i+K-1]-arr[i]:
        ans=arr[i+K-1]-arr[i]

print(ans)

Measured memory_bytes: 8276
N,M=map(int,input().split())
A=[input() for i in range(N)]
B=[input() for i in range(M)]
def F(a,b):
  for k in range(M):
    for l in range(M):
      if A[a+l][b+k]!=B[l][k]:
        return False
  return True
  
for i in range(N-M+1):
  for j in range(N-M+1):
    if F(i,j):
      print('Yes')
      exit()
print('No') 

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

using namespace std;

int main(){
  int N,K,num;
  cin >> N >> K;
  int i,j,d,a[N];
  for(i=0;i<N;i++){
    a[i]=1;
  }
  for(i=0;i<K;i++){
    cin >> d;
    for(j=0;j<d;j++){
      cin >> num;
      a[num-1]=0;
    }
  }
  int ans=0;
  for(i=0;i<N;i++){
    ans+=a[i];
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int main()
{
  int n,k;cin >> n >> k;
  string s;cin >> s;
  vector<int> a;
  int cnt = 1;
  rep(i,n-1){
    if(s[i] == s[i+1]) cnt++;
    else{
      a.push_back(cnt);
      cnt = 1;
    }
  }
  a.push_back(cnt);
  int res = 0;
  int as = a.size();
  rep(i,as) res += a[i] - 1;
  int x = ( as - 1 ) / 2;
  if(as % 2 == 0){
    if( x + 1 <= k ) res += 2 * x + 1;
    else if( x <= k ) res += 2 * x;
    else res += 2 * k;
  }
  else {
    if( x <= k ) res += 2 * x;
    else res += 2 * k;    
  }
  cout << res << "\n";
  return 0;
}


Measured memory_bytes: 1020
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define crep(i) for(char i='a';i<='z';i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

set<ll> S;
queue<ll> Q;

int main(){
    ll N,K,A[200007],C=0,T=0,Z=0;cin>>N>>K;
    rep(i,N){
        cin >> A[i];
        if(i>0 && A[i]>A[i-1]){
            T++;
            if(T>=K-1){
                if(i>=K){
                    Q.push(i);
                }
                Z++;
            }
        }
        else{
            T=0;
        }
    }
    rep(i,N){
        S.insert(A[i]);
        if(i>=K){
            if(Q.empty()!=1){
                if(i==Q.front()){
                    S.erase(A[i-K]);
                    Q.pop();
                    continue;
                }
            }
            if(*S.begin()==A[i-K] && *S.rbegin()==A[i]){
                C++;
            }
            S.erase(A[i-K]);
        }
    }
    cout << N-K+1-C-(max(Z-1,0LL)) << endl;
}

Measured memory_bytes: 11136
#include<iostream>
using namespace std;
int main(){
  int t[110][110];
  int w,h,n; cin >> w >> h >> n;
  for(int i=0;i<n;i++){
    int x,y,a; cin >> x >> y >> a;
       if(a==1){
    	for(int j=0;j<x;j++){
          for(int k=0;k<h;k++) t[j][k]=1;
        }
       }
       if(a==2){
    	for(int j=x;j<w;j++){
          for(int k=0;k<h;k++) t[j][k]=1;
        }
       }
       if(a==3){
    	for(int j=0;j<w;j++){
          for(int k=0;k<y;k++)t[j][k]=1;
        }
       }
       if(a==4){
       for(int j=0;j<w;j++){
         for(int k=y;k<h;k++)t[j][k]=1;
        }
       }
    }  	
  int ans=0;
  for(int i=0;i<w;i++){
    for(int j=0;j<h;j++){
      if(t[i][j]==0) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
#define xx first
#define yy second

double pi=3.141592653589793238;
const int M = 1e9+7;
const int Nmax=5005;
const int MM = 2e5+1;



int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
//cin>>T;
while(T--){
int h,w,k;
cin>>h>>w>>k;
char arr[h][w];
int ans=0;
int cnt=0;
for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
        cin>>arr[i][j];
        if(arr[i][j]=='#')cnt++;
    }
}
for(int i=0;i<(1<<h);i++){
    for(int j=0;j<(1<<w);j++){
        int a[h][w];
        int c=0;
        for(int ii=0;ii<h;ii++){
            for(int jj=0;jj<w;jj++)
                if((i&(1<<ii))||(j&(1<<jj)))a[ii][jj]=0;
                else a[ii][jj]=1;
        }
        for(int ii=0;ii<h;ii++){
            for(int jj=0;jj<w;jj++)
               if(a[ii][jj]==1){
                if(arr[ii][jj]=='#')c++;
               }
        }
        if(c==k)ans++;
    }
}
cout<<ans<<"\n";
}
return 0;
}

/*_*/


Measured memory_bytes: 3636
/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <cstdio>
#include <iostream>
using namespace std;
int main(){
    int x,a,b;
    cin >>  x >> a >> b;
    if(b-a<=0){
        printf("delicious");
    }
    else if(b-a>x){
        printf("dangerous");
    }
    else{
        printf("safe");
    }
}



Measured memory_bytes: 3648
#include <iostream>

int main(void) {
    int N, M;
    bool flag=false;
    std::cin >> N;
    M = N;

    while (M >= 0) {
        if (M % 4 == 0) {
            flag = true;
        }
        M -= 7;
    }

    if(!flag) {
        while (N >= 0) {
            if (N % 7 == 0) {
                flag = true;
            }
            N -= 4;
        }
    }

    if (flag) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int dice[6][5] = {{1, 5, 4, 2, 3}, {2, 1, 4, 6, 3},{3, 1, 2, 6, 5}, {4, 1, 5, 6, 2}, {5, 1, 3, 6, 4}, {6, 2, 4, 5, 3}};
    int up, right, front;
    int q;
    int i, j;
    int upStop, rightStop;

    for(i = 0; i < 6; i++){
        scanf("%d", &dice[i][0]);
    }

    scanf("%d", &q);

    for(i = 0; i < q; i++){
        scanf("%d%d", &up, &right);
        up;
        right;
        for(upStop = 0; upStop < 6; upStop++){
            if(dice[upStop][0] == up)   break;
        }
        //printf("found up : %d\n", dice[upStop][0]);
        for(rightStop = 1; rightStop < 5; rightStop++){
            if(dice[(dice[upStop][rightStop]) - 1][0] == right) break;
        }
        //printf("found right : %d\n", dice[(dice[upStop][rightStop]) - 1][0]);
        if(rightStop == 4) rightStop = 1;
        else rightStop++;
        front = dice[(dice[upStop][rightStop] - 1)][0];
        printf("%d\n", front);
    }
    return (0);
}


Measured memory_bytes: 2036
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long floor_sum(long long n, long long m, long long a, long long b) {
    long long sum = 0;
    if (a >= m) {
        sum += (a / m) * n * (n - 1) / 2;
        a %= m;
    }
    if (b >= m) {
        sum += (b / m) * n;
        b %= m;
    }
    long long y = (a * n + b) / m;
    long long x = y * m - b;
    if (y == 0) return sum;
    sum += (n - (x + a - 1) / a) * y;
    sum += floor_sum(y, a, m, (a - x % a) % a);
    return sum;
}

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

    int T;
    cin >> T;
    while (T--) {
        int N, M, A, B;
        cin >> N >> M >> A >> B;
        cout << floor_sum(N, M, A, B) << "\n";
    }
}

Measured memory_bytes: 3668
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

#define int long long
bool sS(const pair<int,int> &a,const pair<int,int> &b)
{
    return(a.second<b.second);
}
int32_t main()
{
    int n,m;cin>>n>>m;
    vector<pair<int,int>> v;
    for(int i=0;i<m;i++)
    {
        int t,t1; cin>>t>>t1;
        v.push_back(make_pair(t,t1));
    }
    int mi,ma;
    sort(v.begin(),v.end());
    mi=v[m-1].first;
    sort(v.begin(),v.end(),sS);
    ma=v[0].second;
    int temp=ma-mi+1;
    if(temp<=0) cout<<0;
    else cout<<temp;
    return 0;
}


Measured memory_bytes: 2420
import sys
import bisect

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7
# mod = 998244353


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    K = int(input())
    N = 50
    M = K // N
    m = K % N
    k = N - m
    A = [N + M - (N - k + 1)] * k + [N + M + k] * (N - k)
    print(N)
    print(" ".join(map(str, A)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include<stdio.h>
int search(int s[],int n,int key){
	int i=0;
	s[n]=key;
	while(s[i]!=key){
		i++;
	}
	return i!=n;
}
int main(){
	int n,s[10000+1],q,i,key,sum=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&s[i]);
	}
	scanf("%d",&q);
	for(i=0;i<q;i++){
		scanf("%d",&key);
		if(search(s,n,key)){
			sum++;
		}
	}
	printf("%d\n",sum);
	return 0;
}


Measured memory_bytes: 2108
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using namespace std;
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PI 3.1415926535897932384626433832795
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
long long MOD = 998244353;
pair<int,int> dx[4] = {{1,0},{-1,0},{0,1},{0,-1}};
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
//uniform_int_distribution(0,1)(rng)
string toString(long long x)
{
stringstream ss;
ss << x;
string str = ss.str();
return str;
}
long long fastpow(long long x,long long k)
{
    if(!k)
        return 1;
    if(k & 1)
        return ((x * fastpow(x,k-1) % MOD) % MOD) % MOD;
    long long ans = fastpow(x,k/2);
    ans %= MOD;
    ans *= ans;
    ans %= MOD;
    return ans;
}
long long sumF(long long x)
{
    int s = 0;
    while(x)
        s += x%10,x /= 10;
    return s;
}
int main()
{
    IO;
   // freopen("hello.in","r",stdin);
    int a,b;
    cin >> a >> b;
    cout << max(a+b,max(2*a - 1,2*b - 1));
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  int k;
  cin>>n;
  cin>>k;
  int a[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  if(n==0)
    cout<<0;
  else if(n==1)
    cout<<abs(a[1]-a[0]);
  else{
  int b[n];
  b[0]=0;
  b[1]=abs(a[1]-a[0]);
    for(int i=2;i<n;i++)
      b[i]=INT_MAX;
  for(int i=2;i<n;i++){
    for(int j=1;j<=k&&(i-j)>=0;j++){
    b[i]=min(b[i],b[i-j]+abs(a[i]-a[i-j]));
    }
  }
   cout<<b[n-1];
  }
  return 0;
}

Measured memory_bytes: 1024
#161d
import math
import copy

K = int(input())

keta = 1
lunlun_numbers_list = [1,2,3,4,5,6,7,8,9]
lunlun_numbers_numer = 9

if K <=9:
    print(lunlun_numbers_list[K-1])
else:
    while 1:
        new_lunlun_numbers_list = list()
        for lower_keta in lunlun_numbers_list:
            ketasu = int(math.log10(lower_keta)//1 + 1)

            if lower_keta>=10:
                last_keta = lower_keta - ((lower_keta//10) * 10)
            else:
                last_keta = lower_keta

            #print(lower_keta,ketasu,last_keta)

            if last_keta !=0: 
                new_lunlun_numbers_list.append(lower_keta*10 + last_keta - 1)
            
            new_lunlun_numbers_list.append(lower_keta*10 + last_keta)

            if last_keta !=9:
                new_lunlun_numbers_list.append(lower_keta*10 + last_keta + 1)

        if len(new_lunlun_numbers_list)+lunlun_numbers_numer >= K:
            new_lunlun_numbers_list.sort(reverse=False)
            print(new_lunlun_numbers_list[K-lunlun_numbers_numer-1])
            #print(new_lunlun_numbers_list)
            break
        else:
            lunlun_numbers_numer+=len(new_lunlun_numbers_list)

        lunlun_numbers_list = copy.copy(new_lunlun_numbers_list) 

Measured memory_bytes: 11692
N, T = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
A, B = map(list, zip(*AB))

dp = {0: 0}
for i in range(N):
    prev_dp = dp.copy()
    for a in prev_dp.keys():
        if a >= T or (a + A[i] in dp and dp[a + A[i]] >= prev_dp[a] + B[i]):
            continue
        dp[a + A[i]] = prev_dp[a] + B[i]
print(max(dp.values()))


Measured memory_bytes: 119384
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

res_ = min([x%10 if x%10!=0 else 10 for x in [a,b,c,d,e]])
sum_ = sum([10*(1+x//10) if (x%10!=0) else x for x in [a,b,c,d,e]])

print(sum_ + res_ - 10)

Measured memory_bytes: 3064
f,h=range,input
R,C,K=map(int,h().split())
G=[[0]*-~C for i in f(R+1)]
for i in'_'*K:r,c,v=map(int,h().split());G[r][c]=v
F=[[[0]*-~C for i in f(R+1)]for i in f(4)]
for r in f(1,R+1):
	for x in f(1,4):
		for c in f(1,C+1):F[x][r][c]=max(F[x-1][r][c],max(F[x-1][r][c-1],(x<2)*F[3][r-1][c])+G[r][c],F[x][r][c-1])
print(F[3][R][C])

Measured memory_bytes: 428412
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int field[2][550][550];
int column[2][550];
int row[2][550];
int cross[2][2];
int win[2];
map<int, i_i> mp[2];

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> win[0] >> win[1] >> m;
    for(int i = 0; i <= 1; i++) {
        for(int y = 1; y <= n; y++) {
            for(int x = 1; x <= n; x++) {
                cin >> field[i][x][y];
                mp[i][field[i][x][y]] = {x, y};
            }
        }
    }
    bool end = false;
    while(m--) {
        int val;
        cin >> val;
        for(int index = 0; index <= 1; index++) {
            if(mp[index][val].first == 0) continue;
            int x = mp[index][val].first;
            int y = mp[index][val].second;
            column[index][x]++;
            row[index][y]++;
            if(column[index][x] == n) win[index]--;
            if(row[index][y] == n) {
                if(n >= 2) win[index]--;
            }
            if(x == y) {
                cross[index][0]++;
                if(cross[index][0] == n && n >= 2) win[index]--;
            } 
            if(x + y == n + 1) {
                cross[index][1]++;
                if(cross[index][1] == n && n >= 2) win[index]--;
            }
        }
        //cerr << val << " " << win[0] << " " << win[1] << endl;
        if(win[1] <= 0 && win[0] > 0) {
            end = true;
            cout << "NEKO" << endl;
            break;
        }
        if(win[0] <= 0 && win[1] > 0) {
            end = true;
            cout << "USAGI" << endl;
            break;
        }
    }
    if(!end) cout << "DRAW" << endl;
    return 0;
}



Measured memory_bytes: 24224
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define mp make_pair
#define pb push_back
#define pf push_front
#define ss second
#define ff first
#define sz(x) (int)x.size()
#define newl "\n"
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define vl vector<ll>
#define pll pair<ll, ll>
#define vll vector<pll>
#define coutp cout << fixed << setprecision(12)
#define mem(x, val) memset(x, val, sizeof(x))
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define all(v) (v).begin(), (v).end()

const ld pi = 3.14159265359;
ll INF = 1e18 + 10;
ll MOD = 998244353;
ll mod = 1e9 + 7;

inline ll add(ll a, ll b, ll m)
{
    if ((a + b) >= m)
        return (a + b) % m;
    return a + b;
}

inline ll mul(ll a, ll b, ll m)
{
    if ((a * b) < m)
        return a * b;
    return (a * b) % m;
}

ll power(ll x, ll y, ll m)
{
    ll res = 1;
    x = x % m;
    if (x == 0)
        return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % m;
        y = y >> 1;
        x = (x * x) % m;
    }
    return res;
}

void solve()
{
    ll n,d;
    cin>>n>>d;
    d*=d;
    //vll a(n);
    int cnt=0;
    for(int i=0;i<n;i++) {
        ll x,y;
        cin>>x>>y;
        ll v = x*x+y*y;
        if(v<=d) cnt++;
    }
    cout<<cnt;
}

int main()
{
    fastio;
    int t;

    t = 1;
    //cin >> t;
    //int test=t;
    while (t-- > 0)
    {
        //cout<<"Case #"<<(test-t)<<": ";
        solve();
        cout << newl;
    }

    return 0;
}

Measured memory_bytes: 3620
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0]*(n+1)
tmp = 0
tmp_2 = 0

for i in range(1,n+1):
    if b[n-i] + c[n+1-i] - a[n+1-i] > 0:
        tmp = b[n-i]+ c[n+1-i] - a[n+1-i]
        c[n+1-i] = a[n+1-i]
    else:
        c[n+1-i] = b[n-i]+c[n+1-i]
        tmp = 0
        continue

    if tmp - a[n-i] > 0:
        c[n-i] = a[n-i]
        #tmp_2 = tmp - a[n-i]
    else:
        c[n-i] = tmp
        #tmp_2 = 0

print(sum(c))

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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

vector<ll> solve(int N, const vector<ll>& xs)
{
    ll all = 0;

    for (int i = 1; i < N; ++i)
        all ^= (xs[0] ^ xs[i]);

    vector<ll> ans(N);

    for (int i = 0; i < N; ++i)
        ans[i] = all ^ xs[i];
 
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    vector<ll> xs(N);

    for (int i = 0; i < N; ++i)
        cin >> xs[i];

    auto ans = solve(N, xs);

    for (int i = 0; i < N; ++i)
        cout << ans[i] << (i + 1 == N ? '\n' : ' ');

    return 0;
}


Measured memory_bytes: 6272
#pragma GCC optimize "O3"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define POP pop_back
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define F first
#define S second
#define X real()
#define Y imag()
#ifndef LOCAL
    #define endl "\n"
#endif

using namespace std;
using namespace chrono;
using namespace __gnu_pbds;

typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef long long C;
typedef complex<C> P;

const int INF = 1e9;
const long long LLINF = 1e18;
const double PI = 3.14159265358979323;
const long long PRIME = (1ll << 31) - 1;
const long long PRIME2 = 269;
const long long MOD = 1e9 + 7;

template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using hash_set = gp_hash_table<T, null_type>;
template <class T, class U> using hash_map = gp_hash_table<T, U>;
template <class T, class U> ostream& operator<< (ostream &out, pair<T, U> p) { return out << "(" << p.F << ", " << p.S << ")"; }
template <class T> ostream& operator<< (ostream &out, vector<T> c) { for (auto it = c.begin(); it != c.end(); ++it) { if (it != c.begin()) out << " "; out << *it; } return out; }
template <class T> ostream& operator<< (ostream &out, set<T> c) { for (auto it = c.begin(); it != c.end(); ++it) { if (it != c.begin()) out << " "; out << *it; } return out; }
template <class T, class U> ostream& operator<< (ostream &out, map<T, U> c) { for (auto it = c.begin(); it != c.end(); ++it) { if (it != c.begin()) out << " "; out << *it; } return out; }
template <class T> ostream& operator<< (ostream &out, ordered_set<T> c) { for (auto it = c.begin(); it != c.end(); ++it) { if (it != c.begin()) out << " "; out << *it; } return out; }
template <class T, class U> ostream& operator<< (ostream &out, ordered_map<T, U> c) { for (auto it = c.begin(); it != c.end(); ++it) { if (it != c.begin()) out << " "; out << *it; } return out; }
template <class T> ostream& operator<< (ostream &out, hash_set<T> c) { for (auto it = c.begin(); it != c.end(); ++it) { if (it != c.begin()) out << " "; out << *it; } return out; }
template <class T, class U> ostream& operator<< (ostream &out, hash_map<T, U> c) { for (auto it = c.begin(); it != c.end(); ++it) { if (it != c.begin()) out << " "; out << *it; } return out; }
template <class T> int sign (T x) { return (x > 0) - (x < 0); }
inline ll mod (ll a, ll b) { return a%b + (a < 0) * b; }
inline ll mod (ll a) { return mod(a, MOD); }
C dot (P a, P b) { return a.X * b.X + a.Y * b.Y; }
C cross (P a, P b) { return a.X * b.Y - b.X * a.Y; }

double startTime;
double currTime() { return duration_cast<nanoseconds>(system_clock::now().time_since_epoch()).count() / 1e9; }
double execTime() { return currTime() - startTime; }

int main() {
#ifndef LOCAL
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#endif
    srand(time(0));
    startTime = currTime();

    string s;
    cin >> s;

    cout << string(s.size(), 'x') << endl;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	
	public static long gcd(long a, long b){
		if(b == 0){ return a; }
		else {return gcd(b, a % b);}
	}
	
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		final long a = sc.nextLong();
		final long b = sc.nextLong();
		
		System.out.println(gcd(a, b));
		
	}
}

Measured memory_bytes: 17352
import java.io.*;
import java.util.*;

public class Main {
  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static int[][] arr, indices;
  static int[] prefix;
  
	public static void main (String[] args) throws IOException {    
    String[] first = br.readLine().split(" ");
    int H = Integer.parseInt(first[0]);
    int W = Integer.parseInt(first[1]);
    int D = Integer.parseInt(first[2]);
    
    arr = new int[H][W];
    indices = new int[H*W+1][2];
    prefix = new int[H*W+1];
    
    for(int i = 0; i < H; i++) {
      String[] line = br.readLine().split(" ");
      for(int j = 0; j < W; j++) {
        int curr = Integer.parseInt(line[j]);
        arr[i][j] = curr;
        indices[curr] = new int[]{i+1, j+1};
      }
    }
      
    for(int j = 1; j <= H*W; j++) {
      if(j + D <= H*W) {
        int[] a = indices[j];
        int[] b = indices[j+D];
        int curr = Math.abs(b[0]-a[0]) + Math.abs(b[1]-a[1]);
        if(j - D <= 0) {
          prefix[j] = curr;
        }
        else {
          prefix[j] = prefix[j-D] + curr;
        }
      }
    }
    
    int Q = Integer.parseInt(br.readLine());
    
    for(int i = 0; i < Q; i++) {
      String[] line = br.readLine().split(" ");
      int L = Integer.parseInt(line[0]);
      int R = Integer.parseInt(line[1]);
      
      int ans = 0;
      
      if(R < D) {}
      else if(L < D) {
        ans = prefix[R-D];
      }
      else {
        ans = prefix[R-D]-prefix[L-D]; 
      }
      
      bw.write(ans + "\n");
    }
    
    bw.close();
	}
}


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

const int N = 1e5 + 1;

#define int long long

int dp[403][403];
int n, a[401], pr[401];

int calc(int l, int r)
{
	if(l >= r) return 0;
	if(dp[l][r] != 4557430888798830399) return dp[l][r];
	for(int i = 0; l + i <= n; i++)
		dp[l][r] = min(calc(l, l + i) + calc(l + i + 1, r) + pr[r] - pr[l - 1], dp[l][r]);
		
	return dp[l][r];
}

main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	
	for(int i = 1; i <= n; i++)
		pr[i] = pr[i - 1] + a[i];
	
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	
	calc(1, n);
	
	cout << dp[1][n] << endl;
}


Measured memory_bytes: 1536
#include <iostream>

using namespace std;

void call(int n);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    call(n);
    return 0;
}


void call(int n){
    for(int i=1; i<=n; i++) {
        int x = i;
        if ( x % 3 == 0 ){
            cout << " " << i;
            continue;
        }
        do {
            if ( x % 10 == 3 ){
                cout << " " << i;
                break;
            }
        x /= 10;
        }while( x );
    }

    cout << endl;
}

Measured memory_bytes: 1200
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int n;cin>>n;
    int a[n+1];
    int b=0,c=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b+= 2 *a[i];
        c+=a[i]*a[i];
    }
    int k1=ceil((double) b/(double)(2*n) ),k2=floor  ( (double)b/ (double)(2*n));
    cout<<min(   (  n*k1*k1-b*k1+c   )   ,( n*k2*k2-b*k2+c )      ); 
    return 0;
}


Measured memory_bytes: 256
n=int(input())
memo={}
for i in range(n):
  s=input()
  if s not in memo:
    memo[s]=1
  else:
    memo[s]+=1
    
a=[]
max_v = max(memo.values())
for k, v in memo.items():
  if v==max_v:
    a.append(k)
print('\n'.join(sorted(a)))

Measured memory_bytes: 97040
# C - Multiplication 3
str_a, str_b = input().split()

a = int(str_a)
#print(a)

# 小数点を外した後 数値化することで、Bを誤差なく100倍できる
b = int(str_b.replace('.', ''))
#print(b)

print(a * b // 100)

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

const ll INF = 1LL << 60;

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

ll N, K;
int main() {
    cin >> N >> K;

    // combination comb = combination(3 * 10e5);
    // cout << comb(4, 2) << endl;
    vector<ll> sum(N + 2);
    rep(i, N + 1) {
        sum[i + 1] = sum[i] + i;
    }

    // rep(i, N + 2) {
    //     cout << sum[i] << endl;
    // }

    mint ans = 0;
    for (int i = K; i <= N; i++) {
        // cout << i << " " << sum[i] << " " << sum[N + 1] - sum[N - i] << endl;
        // cout<< sum[N + 1] - sum[N - i] << " " << sum[i] << endl;
        ll start = sum[i];
        ll end = sum[N + 1] - sum[N - i + 1];
        // cout << start << " " << end << endl;
        // cout << end - start + 1 << endl;
        ans += end - start + 1;
    }
    ans += 1;
    cout << ans << endl;
}

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

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

ll lcm(ll a, ll b){
  return a/gcd(a,b) * b;
}
ll func2(ll n){
  ll res = 0;
  while(n%2 == 0){
    n /= 2;
    res++;
  }
  return res;
}

ll zyou(ll a,ll b){//a＾b
  ll res = 1;
  for(int i = 1;i<=b;i++){
    res *= a;
  }
  return res;
}
struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t),weight(w){ }
};

typedef pair<int,int> P;
using Graph = vector<vector<int>>;

ll calc(ll a, ll b, ll p){//aのb乗をpで割った余り
  if(b == 0) return 1;

  else if(b%2 == 0){
    ll d = calc(a,b/2,p);
    return (d*d)%p;
  }
  else if(b%2 == 1){
    return (a * calc(a,b-1,p))%p;
  }
}


bool is_prime(int n){//nが素数であるかどうか判定 iで割り切れると素数でない
    if(n == 1) return false;//1は例外
    for(int i = 2;i*i <= n;i++){
        if(n%i == 0) return false;
    }
    
    return true;
}

bool palin(string S){//回文判定
  int n = S.size();
  bool flag = true;
  if(n%2 == 0){
    for(int i = 0;i<=n/2-1;i++){
      if(S[i] != S[n-i-1]){
        flag = false;
        break;
      }
    }
  }
  else if(n%2 == 1){
    for(int i = 0;i<=n/2-1;i++){
      if(S[i] != S[n-i-1]){
        flag = false;
        break;
      }
    }
  }
  return flag;
}
vector<int> d(2000+1,-1);

//頂点xとの各点との最短距離を求める
void bfs(int x,Graph &G){
  d[x] = 0;
  queue<int> que;
  que.push(x);

  // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (d[nv] != -1) continue; // すでに発見済みの頂点は探索しない

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            d[nv] = d[v] + 1;
            que.push(nv);
        }
    }
}

int main(){
  int N,X,Y;
  cin >> N >> X >> Y;
  Graph G(N+1);
  G[1].push_back(2);
  G[N].push_back(N-1);

  for(int i = 2;i<=N-1;i++){
    G[i].push_back(i-1);
    G[i].push_back(i+1);
  }
  G[X].push_back(Y);
  G[Y].push_back(X);

  /*for(int i = 0;i<N+1;i++){
    for(int j = 0;j<G[i].size();j++){
      cout << G[i][j] << " ";
      if(j == G[i].size()-1) cout << endl;
    }
  }*/
  vector<int> ans(N);
  for(int i = 1;i<=N;i++){
    bfs(i,G);
    for(int j = 1;j<=N;j++){
      ans[d[j]]++;
    }
    for(int j = 1;j<=N;j++){
      d[j] = -1;
    }
  }
  for(int i = 1;i<=N-1;i++){
    cout << ans[i]/2 << endl;
  }
 }

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

int main()
{
    long long N, M;
    cin >> N >> M;

    long long A = 0, a = 0;
    for (int i = 0; i < M; i++) {
        cin >> a;
        A = A + a;
    }

    if (N >= A) {
        cout << N - A;
    } else {
        cout << -1;
    }
}

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

const int INF = 1001001001;

int x[110];
int y[110];

int func(int x){
  int sum=0;
  while(x!=0){
    sum+=x%10;
    x/=10;
  }
  return sum;
}
int main() {
 int N,A,B;
 cin>>N>>A>>B;
 int ans=0;
 for(int i=1;i<=N;i++){
 int t=func(i);
 if(t>=A&&t<=B){ans+=i;}
 }
 cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cctype>
using namespace std;

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int N, P;
map<string,int> all[7];
map<string,int> weeks;
bool flag[7][3100];

int main() {
  while (cin>>N, N) {
    rep(i,7) all[i].clear();
    weeks.clear();
    {
      string name;
      int week, start;
      rep(i,N) {
        cin>>name>>week>>start;
        all[week].insert(make_pair(name,start/100*60+start%100));
        weeks.insert(make_pair(name,week));
      }
      cin>>P;
      memset(flag, false, sizeof flag);
      //vector<string> fav;
      set<string> fav;
      bool ok  = true;
      rep(i,P) {
        cin>>name;
        //fav.push_back(name);
        fav.insert(name);
        int week = weeks[name];
        int offset = all[week][name];
        if (flag[week][offset] || flag[week][offset+29]) { ok = false; }
        if (!ok) { continue; }
        for (int j = offset; j < offset+30; ++j) flag[week][j] = true;
      }
      if (!ok) { puts("-1"); continue; }

      //sort(fav.begin(), fav.end());
      rep(i,7) {
        set<int> s;
        foreach(all[i],itr) {
          // if(!binary_search(fav.begin(), fav.end(), itr->first)) {
          //   if (s.count(itr->second)) s.insert(itr->second);
          // }
          if (!fav.count(itr->first)) {
            s.insert(itr->second);
          }
        }
        //cout<<"["<<s.size()<<"]"<<endl;
        foreach(s,itr) {
          int v = *itr;
          //cout<<"("<<v<<")"<<endl;
          if (flag[i][v] || flag[i][v+29]) continue;
          for (int j = v; j < v+30; ++j) flag[i][j] = true;
        }
      }

      int ret = 0;
      rep(i,7) {
        for (int j = 0; j < 3000; ++j) {
          if (!flag[i][j]) continue;
          //cout << i << "," <<j << endl;
          ++ret;
          j += 29;
        }
      }
      cout << ret << endl;
    }
  }
  return 0;
}

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

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


Measured memory_bytes: 3084
#include<bits/stdc++.h>
#define ll long long
#define N 100005
#define M 1000000007
#define pii pair<ll,ll>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
main()
{
    int n,m;
    cin>>n>>m;
    cout<< (m*(m-1))/2+(n*(n-1))/2;

}


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

using namespace std;

int main()
{
	int N;
	cin >> N;
	vector<string> W(N);
	for (int i = 0; i < N; i++)
	{
		cin >> W[i];
	}
	
	bool isOK = true;
	
	// その単語の先頭の文字は直前に発言した単語の末尾の文字が一致しているかのチェック
	for (int i = 0; i < N - 1; i++)
	{		
		char last = W[i].back();
		char first = W[i + 1].front();
		// 一致していない場合
		if (last != first)
		{
			isOK = false;
		}
	}
	
	// その単語はまだ発言していない単語チェック
	for (int i = 0; i < N; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			if (W[i] == W[j])
			{
				isOK = false;
			}
		}
	}
	
	if (isOK) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	
	return 0;
}


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


int main(void)
{
	int a, b;
	cin >> a >> b;
	if (a == b){
		cout << "a == b"<< endl;
	}
	else if (a > b){
		cout << "a > b" << endl;
	}
	else if (a < b){
		cout << "a < b" << endl;
	}
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

//Do not get frustrated over WA. Check for edge cases and runtime errors :)
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, a, b;
    cin >> n >> a >> b;

    ll x = n / (a + b), mod = n % (a + b), ans = x * a;
    cout << ans + min(mod, a);
    return 0;
}

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

int main(){
  int n,m;
  cin >> n >> m;
  vvi graph(n+1);
  rep(i,m){
    int a,b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  vi dist(n+1, -1);
  queue<int> que;
  dist[1] = 0;
  que.push(1);
  while(!que.empty()){
 //   cout << 1;
    int v = que.front();
    que.pop();
    for(int nv : graph[v]){
      //cout << 2;
      if(dist[nv] != -1) continue;
      dist[nv] = dist[v] + 1;
      que.push(nv);
    }
  }
  cout << "Yes" << endl;
  for(int i=2; i<=n; i++){
    for(int v : graph[i]){
      if(dist[i] - dist[v] == 1){
        cout << v << endl;
        break;
      }
    }
  }
}


Measured memory_bytes: 10244
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define in insert
#define PI 3.1415926535897932384626433832795
#define F first
#define S second
#define aLL(str) (str).begin(), (str).end()
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0)
#define ll long long
#define ld long double
#define lcm(a, b) (a * b) / __gcd(a, b)
#define flu(i, a, b) for (ll i = a; i < b; i++)
#define blu(i, a, b) for (ll i = a; i >= b; i--)
#define upper(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define Unique(X) (X).erase(unique(all(X)), (X).end())
#define all(v) v.begin(), v.end()
typedef vector<ll> vl;
typedef map<ll, ll> ml;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
char e = '\n';

ll MOD = 1e9 + 7;

ll i, j, le;

int sv(int x)
{
    int n = 200000;
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));

    for (int p = 2; p * p <= n; p++)
    {
       
        if (prime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    if (prime[x])
        return 1;
    else
        return 0;
}

int main()
{
    IOS;
    int t;
    //cin >> t;
 t=1;
    while (t--)
    {
        ll n,x,t;
        cin>>n>>x>>t;
        ll ans = (n/x)*t;
        ll left = n%x;
        if(left >=1)ans+=t;
        cout<<ans<<e;
    }
    return 0;
}

Measured memory_bytes: 3604
n=int(input())
A=[1,1]
for i in range(n):
  t,a=map(int,input().split())
  tt=(A[0]+t-1)//t
  aa=(A[1]+a-1)//a
  A[0]=max(tt,aa)*t
  A[1]=max(tt,aa)*a
print(A[0]+A[1])

Measured memory_bytes: 3060
# 'A'=0, 'C'=1, 'G'=2, 'T'=3 の4進法で考える
p=10**9+7
N=int(input())

a=[[0 for i in range(101)] for x in range(64)]
# a[x][i]は，最後の3桁がxであるようなi桁の文字列の数
# i=3での初期値
for x in range(64):
    if x in [6,9,33]:
        a[x][3]=0
    else:
        a[x][3]=1

# 漸化式
for i in range(3,N):
    for x in range(64):
        if x in [9,33,6]: # XAGC,XGAC,XACG
            a[x][i+1]=0
        elif x in [25,41,57,37,45]: # AXGC(A-:AGC(既出),CGC,GGC,TGC),AGXC(A-:GAC(既出),GCC,GGC(既出),GTC)
            a[x][i+1]=(a[x//4+16][i]+a[x//4+32][i]+a[x//4+48][i])%p
        else:
            a[x][i+1]=(a[x//4][i]+a[x//4+16][i]+a[x//4+32][i]+a[x//4+48][i])%p

ans=0
for x in range(64):
    ans+=a[x][N]
print(ans%p)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;

  void seive(vector<int>&fact,int n,vector<int>a,int r)
  {
      int i=0;
      while(i<n)
      {
      int k=a[i];

      for(int j=k;j<=r;j+=k)
      {
          //cout<<j<<endl;
          fact[j]++;
      }
      i++;
      }

  }

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

      int n;
      cin>>n;
      vector<int>a(n);
      for(int i=0;i<n;i++)
        cin>>a[i];

      sort(a.begin(),a.end());
      int r=a[n-1];
      vector<int>fact(r+1,0);
      seive(fact,n,a,r);
      int cnt=0;
      for(int i=0;i<n;i++)
      {
          if(fact[a[i]]<2)
            cnt++;
      }
      cout<<cnt<<endl;

    return 0;
  }


Measured memory_bytes: 8704
function main(s) {
    var r = s.trim().split("");
    var inject = [0, 4, 6, 8];
    for (var i = 0; i < inject.length; i++)
        if (r[inject[i]] !== 'A') r.splice(inject[i], 0, "A");
    console.log(r.join("") === "AKIHABARA" ? "YES" : "NO");
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

#define sci(a) scanf("%d", &a)
#define fto(i, a, b) for (int i = a; i <= b; ++i)
#define fdto(i, a, b) for (int i = a; i >= b; --i)
#define scii(a, b) scanf("%d %d", &a, &b)
#define ll long long
#define ff first
#define ss second
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define pii pair<int, ii>
#define maxN 100005
#define oo 1000000007
#define mp make_pair
#define pb push_back
#define bug(a) cout << #a << "= " << a << endl;
#define bug2(a, b) cout << #a << "= " << a << "; " << #b << "= " << b << endl
#define pri(a) printf("%d", a)
#define pril(a) printf("%d\n", a)

using namespace std;

ll ans;
int n, m, a[maxN];
ii p[maxN], canh[maxN];
vector<ll> kq;

void initSet(int n) {
    fto(i, 1, n) p[i] = mp(i, 1);
}
int findSet(int i) {
    if(p[i].ff == i) return i;
    return p[i].ff = findSet(p[i].ff);
}
void unionSet(int i, int j) {
    int x = findSet(i);
    int y = findSet(j);
    p[x].ff = y;
    ans -= (ll)p[x].ss*p[y].ss;
//    bug(ans);
    p[y].ss += p[x].ss;
}
int issameSet(int i, int j) {
    return findSet(i) == findSet(j);
}

int main() {
//    #ifndef ONLINE_JUDGE
//    freopen("cf.inp", "r", stdin);
//    freopen("cf.out", "w", stdout);
//    #endif

    scii(n, m);
    fto(i, 1, m) scii(canh[i].ff, canh[i].ss);
    initSet(n);
    ans = n;
    ans *= n-1;
    ans /= 2;
    kq.pb(ans);
    fdto(i, m, 2) {
        int u = canh[i].ff;
        int v = canh[i].ss;
        if(!issameSet(u, v)) {
            unionSet(u, v);
        }
        kq.pb(ans);
    }
    fdto(i, (int)kq.size()-1, 0) cout << kq[i] << '\n';
    return 0;
}


Measured memory_bytes: 3828
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
from typing import *
import collections
import functools as fts
import itertools as its
import math
import sys

INF = float('inf')


def solve(N: int, A: "List[int]"):
    ans = 0
    m = A[0]
    for a in A[1:]:
        ans += max(0, m - a)
        m = max(m, a)
    return ans


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(f'{solve(N, A)}')


if __name__ == '__main__':
    main()


Measured memory_bytes: 100208