akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<list>
using namespace std;
#define inRange(x,a,b) (a <= x && x < b)
int di[8] = {0,0,1,-1,1,1,-1,-1};
int dj[8] = {1,-1,0,0,1,-1,1,-1};

typedef pair<int,int> pii;

// 0-1 bfs
int main(){
    int w, h;
    while(cin >> w >> h, w+h){
        int si, sj, gi, gj, bi, bj;
        int mat[h][w];
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> mat[i][j];
                if(mat[i][j] == 2)  mat[i][j] = 0, bi = i, bj = j;
                if(mat[i][j] == 3)  gi = i, gj = j;
                if(mat[i][j] == 4)  si = i, sj = j;
            }
        }
        vector<vector<int>> d(h*w, vector<int>(h*w, 1<<30));
        list<pair<int,pii>> q;
        q.push_front({0, {si*w+sj, bi*w+bj}});
        d[si*w+sj][bi*w+bj] = 0;
        while(!q.empty()){
            auto p = q.front(); q.pop_front();
            if(d[p.second.first][p.second.second] != p.first)    continue;
            si = p.second.first/w, sj = p.second.first%w;
            bi = p.second.second/w, bj = p.second.second%w;
            for(int k = 0; k < 4; k++){
                int ni = si+di[k], nj = sj+dj[k];
                if(!inRange(ni,0,h)||!inRange(nj,0,w)||mat[ni][nj]==1)  continue;
                if(ni==bi&&nj==bj){
                    int nbi = bi+di[k], nbj = bj+dj[k];
                    if(!inRange(nbi,0,h)||!inRange(nbj,0,w)||mat[nbi][nbj]==1)  continue;
                    if(d[ni*w+nj][nbi*w+nbj] > d[si*w+sj][bi*w+bj]+1){
                        d[ni*w+nj][nbi*w+nbj] = d[si*w+sj][bi*w+bj]+1;
                        q.push_back({d[ni*w+nj][nbi*w+nbj], {ni*w+nj, nbi*w+nbj}});                        
                    }
                }else if(d[ni*w+nj][bi*w+bj] > d[si*w+sj][bi*w+bj]){
                    d[ni*w+nj][bi*w+bj] = d[si*w+sj][bi*w+bj];
                    q.push_front({d[ni*w+nj][bi*w+bj], {ni*w+nj, bi*w+bj}});
                }
            }
        }
        int ans = 1<<30;
        for(int i = 0; i < h*w; i++){
            ans = min(ans, d[i][gi*w+gj]);
        }
        cout << (ans==1<<30 ? -1 : ans) << endl;
    }
    return 0;
}


Measured memory_bytes: 3132
#include <stdio.h>
#include <stdlib.h>

void make(int *);
void rec(int *,int);
int Search(int *,int);

int *A,*m;
int n,q;
int *jdg;
int main() {
  int i;
  int *S;

  scanf("%d",&n);
  A = (int *)malloc(n * sizeof(int));
  for(i=0;i<n;i++) {
    scanf("%d",&A[i]);
  }

  scanf("%d",&q);
  m = (int *)malloc(q * sizeof(int));
   jdg = (int *)malloc(q * sizeof(int));
  for(i=0;i<q;i++) {
    scanf("%d",&m[i]);
    jdg[i] = 0;
  }
  S = (int *)malloc(n * sizeof(int));
  make(S);
  //for(i=0;i<n;i++) printf("%d ",S[i]);
  //make(S,n);
  //for(i=0;i<n;i++) printf("%d ",S[i]);
  
  for(i=0;i<q;i++) {
    if(jdg[i] == 1) printf("yes\n");
    else printf("no\n");
  }
  return 0;
}

void make(int *S) {
  int i,j;
  for(i=0;i<n;i++) {
    for(j=0;j<q;j++) {
      S[i] = 0;
    }
  }
  rec(S,0); 
}

void rec(int *S,int i) {
  int j=0;
  int judge=0;
  if(i==n) {
    //for(int i=0;i<n;i++) printf("%d ",S[i]);
    //printf("%d\n",q);
    for(j=0;j<q;j++) {
      judge = Search(S,m[j]);
      if(judge == 1) jdg[j] = 1;
    }
    //printf("\n");
    return;
  }

  rec(S,i+1);
  *(S+i) = 1;
  
  rec(S,i+1);
  *(S+i) = 0;
  
}

int Search(int *S,int key) {
  int i,j=0;
  int sum=0;
  //for(int i=0;i<n;i++) printf("%d ",S[i]);
  //printf("\n");
  for(i=0;i<n;i++) {
    if(S[i] == 1) {
      sum+=A[i];
    }
    if(sum == key) return 1;
  }
  return -1;
}




Measured memory_bytes: 2104
#include<iostream>
#include<string>
#include<algorithm>
typedef long long ll;
using namespace std;
int main(void){
   int n,l;
   cin >> n >> l;
   std::string a[n];
   for(int i=0;i<n;++i){
	  cin >> a[i];
   }
   std::sort(a,a+n);
   string sum;
   for(ll i=0;i<n;++i){
	  	sum += a[i]; 
	 }
   cout << sum <<endl;
return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        sc.close();

        if (s.equals("ABC")) {
            System.out.println("ARC");

        } else {
            System.out.println("ABC");
        }

    }

}


Measured memory_bytes: 35696
import java.util.*;


public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        
        String s = sc.next();
        String ans ="NO";
        
        for(int i=0; i<s.length(); i++){
            for(int j=0; j<s.length(); j++){
                String a = s.substring(0,i);
                String b = s.substring(j,s.length());
                if(a.equals("keyence") || b.equals("keyence") || (a+b).equals("keyence")){
                    ans = "YES";
                }
            }
        }
		
		System.out.println(ans);
    }
}


Measured memory_bytes: 42232
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve(args);
    }

    public void solve(String[] args) {
        MyScanner scanner = new MyScanner();
        int N = scanner.nextInt();
        Set<Integer> set = new HashSet<Integer>();
        int b = 0;
        for (int i = 0; i < N; i++) {
            int a = scanner.nextInt();
            int rank = a / 400;
            //System.out.println(rank);
            if (rank >= 8) {
                b++;
            } else {
                set.add(rank);
            }
        }
        int min = set.size();
        if (min == 0) {
            min = 1;
        }
        int max = set.size() + b;
        if (b >= 8) {
            b = 8;
        }
        System.out.println(min+" "+max);
    }

    private class MyScanner {
        String[] s;
        int i;
        BufferedReader br;
        String reg = " ";

        MyScanner () {
            s = new String[0];
            i = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            try {
                if (i < s.length) return s[i++];
                String line = br.readLine();
                while (line.equals("")) {
                    line = br.readLine();
                }
                s = line.split(reg, 0);
                i = 0;
                return s[i++];
            } catch (Exception e) {
                e.printStackTrace();
            }
            return null;
        }

        public int nextInt() {
            try {
                return Integer.parseInt(next());
            } catch (Exception e) {
                e.printStackTrace();
            }
            return -1;
        }

        public double nextDouble() {
            try {
                return Double.parseDouble(next());
            } catch (Exception e) {
                e.printStackTrace();
            }
            return -1;
        }

        public long nextLong()  {
            try {
                return Long.parseLong(next());
            } catch (Exception e) {
                e.printStackTrace();
            }
            return -1;
        }
    }
}


Measured memory_bytes: 21332
# -*- coding: utf-8 -*-
n, q = map(int, input().split())
s = input()
lr = [tuple(map(int, input().split())) for _ in range(q)]

cnt = [0 for _ in range(n)]
for i in range(1, n):
    cnt[i] = cnt[i-1]
    cnt[i] += 1 if s[i-1:i+1] == "AC" else 0

for l, r in lr:
    print(cnt[r-1] - cnt[l-1])


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

#define forn(l, r) for(int i = l; i < (r); ++i)
#define forj(l, r) for(int j = l; j < (r); ++j)
#define TAM 1000100
#define SYNC ios::sync_with_stdio(0);
#define $ << ' ' <<
#define F first
#define S second
#define endl '\n'


using namespace std;

using ll = long long int;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using graph = vector<vi>;
const int INF = 0x3f3f3f3f;
const int MAXN = 112345;
const ll mod = 1000000007;




int main() {
    //SYNC
    int n, num[MAXN], ans = 0;
    double sum = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        sum += num[i];
    }
    sum /= n;
    sum = round(sum);
    for (int i = 0; i < n; ++i) {
        ans += (num[i] - sum)*(num[i] - sum);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n=int(input())
a,b=map(int,input().split())
p=list(map(int,input().split()))
z=[0,0,0]
for t in p:
    if t<=a:
        z[0]+=1
    elif t<=b:
        z[1]+=1
    else:
        z[2]+=1
print(min(z))

Measured memory_bytes: 38384
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"
#define fcout cout << fixed << setprecision(18)

#define MOD 1000000007 // 1e9+7
#define PI 3.1415926535
/*
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
*/
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1
#define LINF 1000000000000000001 // 1e18+1

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
//---------------------------

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  ll n,a,b;cin>>n>>a>>b;
  ll ans;
  if(a>b){
    ans=0;
  }else if(n==1){
    if(a==b){
      ans = 1;
    }else{
      ans=0;
    }
  }else{
    ans = (n-1)*b+a - ((n-1)*a+b) + 1;
  }
  P(ans);
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	static class Burger {
		
		public static long getNumPatties(int level) {
			return pow(2, level+1)-1;
		}
		
		public static long getHeight(int level) {
			return pow(2, level+2)-3;
		}
		
		static long pow(int a, int b) {
			long product = 1;
			while (b > 0) {
				product *= a;
				b--;
			}
			return product;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long X = sc.nextLong();
		
		System.out.println(countPatties(N, X));
		
	}
	
	public static long countPatties(int level, long x) {
		if (x == 0) {
			return 0;
		} else if (level == 0) {
			return 1;
		} else if (x >= Burger.getHeight(level) - level) {
			return Burger.getNumPatties(level);
		}
		
		if (x < Burger.getHeight(level-1)+2) {
			return countPatties(level-1, x-1);
		} else {
			return Burger.getNumPatties(level-1)+1+countPatties(level-1, x-Burger.getHeight(level-1)-2);
		}
	}

}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define ff first
#define ss second
#define p pair<int,int>
#define pb push_back
#define endl '\n'
#define w(t) ll test;cin>>test;while(test--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
#define pi acos(-1)

int main()
{
    ll n,k;
    cin>>n>>k;
    vector<ll>vec(n),ans;
    for(auto &i:vec)cin>>i;
    ll i,sum=1;
    for( i=0;i<k;i++)
    {
        sum*=vec[i];
    }
    ans.pb(sum);
    for(ll j=0;i<n;j++,i++)
    {
       if(vec[i]>vec[j])cout<<"Yes"<<endl;
       else cout<<"No"<<endl;
    }
}



Measured memory_bytes: 4748
#include<iostream>
using namespace std;
int n,A[100];

void trace(){
    for ( int i = 0; i < n; i++ ){
        if ( i ) cout << " ";
        cout << A[i];
    }
     cout << endl;
}
int main(){
    int i,minj,j,cnt;
    cnt =0;
    cin >> n;
    for ( int i = 0; i < n; i++ )cin >> A[i];
    
    for ( i = 0; i < n; i++ ){
        minj = i;
        for ( j = i; j <= n-1; j++ ){
            if ( A[j] < A[minj] ){
                minj = j;                
            }             
        }
        swap( A[i],A[minj] );
        if ( i != minj ){ 
            cnt = cnt+1;     
        }
    }
     trace();    
     cout << cnt << endl;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define INF (1LL<<50)
 
signed main(){
 
	lli n;
	cin>>n;
	vector<lli> v(n),q(n);
	REP(i,0,n){
		cin>>v[i];
		v[i]--;
		q[i] = v[i];
	}
 
	lli ans = INF;
	lli cnt=0;
 
	REP(i,0,n-1){
		if(v[i]==i){
			if(DEBUG)cout<<"v[i] swap!"<<v[i]<<endl;
			swap(v[i],v[i+1]);
			cnt++;
		}
	}
	if(v[n-1]==n-1)swap(v[n-2],v[n-1]),cnt++;
	ans = min(ans,cnt);
	cnt=0;
 
	for(lli i=n-1;i>0;i--){
		if(q[i]==i){
			if(DEBUG)cout<<"q[i] swap!"<<q[i]<<endl;
			swap(q[i],q[i-1]);
			cnt++;
		}
	}
	if(q[0]==0)swap(q[0],q[1]),cnt++;
	ans = min(ans,cnt);
	cout<<ans<<endl;
 
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  long long sum = 0;
  for (int i = 1; i <= n; ++i) {
    if (i % 3 != 0 && i % 5 != 0) {
      sum += i;
    }
  }
  cout << sum << endl;
}


Measured memory_bytes: 3624
/* Simplicity and Goodness */

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

void my_dbg() { cout << endl; }
template<typename Arg, typename... Args> void my_dbg(Arg A, Args... B) { cout << ' ' << A; my_dbg(B...); }
#define dbg(...)  cout << "(" << #__VA_ARGS__ << "):", my_dbg(__VA_ARGS__)

#define scn(n) scanf("%d", &n)
#define lscn(n) scanf("%lld", &n)
#define pri(n) printf("%d ", (int)(n))
#define prin(n) printf("%d\n", (int)(n))
#define lpri(n) printf("%lld ", n)
#define lprin(n) printf("%lld\n", n)
#define rep(i,a,b) for(int i=a; i<(int)b; i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;

const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 1e9+7;
const int maxN = 1e6+2;


int main()
{
   int N, K;
   scn(N); scn(K);

   vi a(N);

   for(int& it : a)
      scn(it);

   const int maxSum = 2502;

   ll dp[N + 1][maxSum][N + 1]; // dp[idx][sum][cnt] - no. of ways to make sum using cnt elements from the first idx elements
   memset(dp, 0, sizeof(dp)); 

   dp[0][0][0] = 1;

   for(int idx = 0; idx < N; idx ++) {
      for(int sum = 0; sum < maxSum; sum ++) {
         for(int cnt = 0; cnt <= idx; cnt ++) {

            dp[idx + 1][sum][cnt] += dp[idx][sum][cnt];

            if(sum + a[idx] < maxSum) 
               dp[idx + 1][sum + a[idx]][cnt + 1] += dp[idx][sum][cnt];
         } 
      }
   }

   ll ans = 0;

   for(int sum = 1; sum < maxSum; sum ++) {
      for(int cnt = 1; cnt <= N; cnt ++) {
         if(cnt * K == sum) {
            ans += dp[N][sum][cnt];
         }
      }
   }

   lprin(ans);

   return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using P = pair<ll, ll>;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
struct edge {
  ll to, cost;
};

int main() {
  int N; cin >> N;
  vector<int> dp(100010, 10000000); dp[0] = 0;
  for(int i = 1; i <= N; ++i) {
    dp[i] = min(dp[i - 1] + 1, dp[i]);
    REP(k, 10) {
      if(i - pow(6, (k + 1)) >= 0) dp[i] = min(dp[i - pow(6, (k + 1))] + 1, dp[i]);
      if(i - pow(9, (k + 1)) >= 0) dp[i] = min(dp[i - pow(9, (k + 1))] + 1, dp[i]);
    }
  }
  cout << dp[N] << endl;
}

Measured memory_bytes: 4088
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

int n, m, q;
int a[50], b[50], c[50], d[50];
int A[10];
int ans = 0;

void solve(int idx, int pre){
	if(idx == n){
		int sum = 0;
		REP(i, q){
			if(A[b[i]] - A[a[i]] == c[i]) sum += d[i];
		}
		ans = max(ans, sum);
		return;
	}
	int tmp = A[idx];
	for(int i = pre; i <= m; i++){
		A[idx] = i;
		solve(idx + 1, i);
	}
	A[idx] = tmp;
}

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	REP(i, q){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		a[i]--; b[i]--;
	}
	solve(0, 1);
	cout << ans << endl;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF (2147483647)
#define MOD (int)(1e9 + 7) 

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    int ans = 0;
    ans += n * (n - 1) / 2;
    ans += m * (m - 1) / 2;
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3600
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Q = sc.nextInt();
        String S = sc.next();
        ArrayList<Integer> List = new ArrayList<>();
        int num=0;
        for(int i=0;i<N-1;i++) {
            char s = S.charAt(i);
            char s2 = S.charAt(i+1);
            if(s=='A'&&s2=='C'){
                List.add(num);
                num+=1;
            }
            else List.add(num);
        }
        List.add(num);
        for(int i=0;i<Q;i++){
            int l = sc.nextInt();
            int r = sc.nextInt();
            int opt =List.get(r-1)-List.get(l-1);
            System.out.println(opt);
        }
    }
}

Measured memory_bytes: 96336
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define test() int t;cin>>t;loop(test,1,t+1)
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define nl cout<<"\n"
#define sp cout<<" "
#define F first
#define S second
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<pii>
#define vll vector<pll>
#define MOD 1000000007
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

void mod( ll &n, ll m=MOD ){ n%=m,n+=m,n%=m; }

const int MAXN = 1e5+5;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

vector<int>gr[MAXN];
bool vis[MAXN];
int dp[MAXN];

void dfs( int node, int par )
{
    vis[node] = 1;
    int ans = 0;
    for( auto next : gr[node] )
    {
        if( !vis[next] )
            dfs(next,node);
        ans = max(ans,dp[next]);
    }
    dp[node] = ans + 1;
}

int main() 
{
    fastio();

    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        u--,v--;
        gr[u].pb(v);
    }

    int mx = 0;
    for(int i=0;i<n;i++)
    {
        if( !vis[i] )
        {
            dfs(i,-1);
            mx = max(mx,dp[i]);
        }
    }
    cout<<mx-1,nl;
    return 0;
}

Measured memory_bytes: 8960
fn main() {
    let n: usize = readln();
    let mut opens = Vec::new();
    for i in 0..n {
        let v: Vec<i32> = readln();
        let mut x = 0;
        for j in 0..10 {
            x = (x << 1) | v[j];
        }
        opens.push(x);
    }

    let costs: Vec<Vec<i64>> = readlns(n);

    let ans = (1..(1 << 10))
        .map(|s| {
            (0..n)
                .map(|i| {
                    let j = (s & opens[i]).count_ones() as usize;
                    costs[i][j]
                })
                .sum::<i64>()
        })
        .max()
        .unwrap();

    println!("{}", ans);
}

// --- template ---
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet};

pub trait FromLn {
    fn fromln(s: &str) -> Self;
}
pub fn readln<T: FromLn>() -> T {
    let mut buf = String::new();
    let _ = ::std::io::stdin().read_line(&mut buf).unwrap();
    T::fromln(buf.trim())
}
pub fn readlns<T: FromLn>(n: usize) -> Vec<T> {
    let mut vs = vec![];
    for _ in 0..n {
        vs.push(readln());
    }
    vs
}
macro_rules! fromln_primitives {
    ($($t:ty),*) => { $(
        impl FromLn for $t {
            fn fromln(s: &str) -> $t {
                s.parse().unwrap()
            }
        }
    )* }
}
fromln_primitives!(
    String,
    bool,
    f32,
    f64,
    isize,
    i8,
    i16,
    i32,
    i64,
    usize,
    u8,
    u16,
    u32,
    u64
);
impl<T> FromLn for Vec<T>
where
    T: FromLn,
{
    fn fromln(s: &str) -> Vec<T> {
        s.split_whitespace().map(T::fromln).collect()
    }
}
impl FromLn for Vec<char> {
    fn fromln(s: &str) -> Vec<char> {
        s.chars().collect()
    }
}
macro_rules! fromln_tuple {
    ($($t:ident),*) => {
        impl<$($t),*> FromLn for ($($t),*) where $($t: FromLn),* {
            fn fromln(s: &str) -> ($($t),*) {
                let mut it = s.split_whitespace();
                let t = ($($t::fromln(it.next().unwrap())),*);
                assert_eq!(it.next(), None);
                t
            }
        }
    }
}
fromln_tuple!(A, B);
fromln_tuple!(A, B, C);
fromln_tuple!(A, B, C, D);
fromln_tuple!(A, B, C, D, E);
fromln_tuple!(A, B, C, D, E, F);


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long lli;
lli n,m;
vector<pair<lli,lli> > ab;
vector<pair<lli,lli> > cd;
int main(){
    cin >> n >> m;
    ab = vector<pair<lli,lli> > (n);cd = vector<pair<lli,lli> > (m+1);
    for(lli i = 0;i < n;i++) cin >> ab[i].first >> ab[i].second;
    for(lli i = 1;i <= m;i++) cin >> cd[i].first >> cd[i].second;
    for(lli i = 0;i < n;i++){
        lli dist = 1ll << 62;
        lli p = 0;
        for(lli j = 1;j <= m;j++){
            if(abs(ab[i].first-cd[j].first)+abs(ab[i].second-cd[j].second) < dist){
                p = j;
                dist = abs(ab[i].first-cd[j].first)+abs(ab[i].second-cd[j].second);
            }
        }
        cout << p << endl;
    }
    return 0;
}

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

int main(){
  int n1,n2,n3,n4,N;
  cin >> N;
  n1 = N / 1000;
  n2 = (N % 1000) / 100;
  n3 = (N % 100) / 10;
  n4 = (N % 10);
  if (n1 == n2 && n2 == n3){
    cout << "Yes" << endl;
  }
  else if (n2 == n3 && n3 == n4){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


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

class Dice {
public:
    static int rollingface[][4];
    int face[6];
    Dice(string &face_data);
    // ~Dice();
    void roll(const char &op);
    int top();
    void print_faces();
};

int Dice::rollingface[][4] = {
    {0, 2, 5, 3},
    {0, 4, 5, 1},
    {0, 1, 5, 4},
    {0, 3, 5, 2},
};

Dice::Dice(string &face_data) {
    istringstream bstrm;
    bstrm.str(face_data);
    for (int i = 0; i < 6; i++) {
        bstrm >> face[i];
    }
}

void Dice::roll(const char &op) {
    int *fseq;
    switch (op) {
        case 'E': fseq = Dice::rollingface[0]; break;
        case 'N': fseq = Dice::rollingface[1]; break;
        case 'S': fseq = Dice::rollingface[2]; break;
        case 'W': fseq = Dice::rollingface[3]; break;
        default: break;
    }
    int t, p = face[fseq[3]];
    for (int i = 0; i < 4; i++) {
        t = face[fseq[i]];
        face[fseq[i]] = p;
        p = t;
    }
}

void Dice::print_faces() {
    cout << "face:" << endl;
    cout << "   " << face[4] << endl;
    cout << face[3] << " " << face[0] << " " << face[2] << endl;
    cout << "   " << face[1] << endl;
    cout << "   " << face[5] << endl;
    cout << endl;
}

int Dice::top() {
    return face[0];
}

int main() {
    string buf, op_seq;
    int i;
    Dice *dice;

    getline(cin, buf);
    dice = new Dice(buf);
    getline(cin, op_seq);
    for (i = 0; i < op_seq.size(); i++) {
        dice->roll(op_seq[i]);
        // dice->print_faces();
    }
    cout << dice->top() << endl;

    return 0;
}

Measured memory_bytes: 1220
import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static int start;
    
    public static boolean nibutan(int array[], int start, int length, int num){
        int pos = -1;
        int lower = start; //最小index番号
        int upper = length - 1; // 最大index番号
        while (lower <= upper) {
            int mid = (lower + upper) / 2;
            if (array[mid] == num) {
                pos = mid;
                break;
            } else if (array[mid] < num) {
                lower = mid + 1;
            } else {
                upper = mid - 1;
            }
        }
        
        if(pos != -1){
            if(pos > 0){
                start = pos - 1;
            }
            return true;
        }else{
            return false;
        }
    }
    
    public static void main(String args[]){
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        int a[] = new int[n];
        start = 0;
        int count = 1;
        boolean flag = true;
        a[0] = stdIn.nextInt();
        for(int i = 1; i < n; i++){ //重複しているところは配列に入れない
            int num = stdIn.nextInt();
            if(a[count - 1] != num){
                a[count++] = num;
            }
        }
        
        int m = stdIn.nextInt();
        int b[] = new int[m];
        
        for(int i = 0; i < m; i++){
            b[i] = stdIn.nextInt();
        }
        
        for(int i = 0; i < m; i++){
            flag = nibutan(a, start, count, b[i]); //左から配列、配列の長さ、探索する数字
            if(!flag){
                break;
            }
        }
        
        if(flag){
            System.out.println(1);
        }else{
            System.out.println(0);
        }
        
        stdIn.close();
    }
}





Measured memory_bytes: 121048
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int insertionSort(int *A, int n, int g);
void shellSort(int *A, int n);
void display(int *A, int N);
void vecdisplay(vector<int> A);

int main(){
    int n;
    cin >> n;
    int A[n];
    for(int i=0; i<n; i++){
        cin >> A[i];
    }
    shellSort(A,n);

}

int insertionSort(int *A, int n, int g){
    int cnt=0;
    for (int i=g; i<n; i++){
        int v=A[i];
        int j = i - g;
        while(j>=0 && A[j]>v){
            A[j+g]= A[j];
            j=j-g;
            cnt+=1;
        }
        A[j+g] = v;
    }
    return cnt;
}

void shellSort(int *A, int n){
    vector<int> G;
    int cnt=0;
    int r=1;
    while(r<=n){
        G.push_back(r);
        r*=2;
    }
    int m=G.size();
    reverse(G.begin(),G.end());
    cout<<m<<endl;
    vecdisplay(G);
    for(int i=0; i<m; i++){
        cnt+= insertionSort(A,n,G[i]);
    }
    cout << cnt << endl;
    for(int i=0; i<n; i++){
        cout << A[i] << endl;
    }
}

void display(int *A, int N){
  for(int i=0; i<N-1 ;i++){
    cout <<A[i] << " ";
  }
  cout << A[N-1] << endl;
}

void vecdisplay(vector<int> A){
  for(int i=0; i<A.size()-1; i++){
    cout <<A[i] << " ";
  }
  cout << A[A.size()-1] << endl;
}



Measured memory_bytes: 7072
#include<bits/stdc++.h>
using namespace std;
#define lps(i,j,n) for(int i=j;i<n;i++)
#define lp(i,n) lps(i,0,n)
#define DEKAI 1000000007
#define INF (1<<28)

signed main(){
  int a[20000],m[20000];
  while(1){
    lp(i,20000){
      m[i]=0;
      a[i]=0;
    }
    int n,mm;
    cin>>n>>mm;
    if(n==0&&mm==0) break;
    lp(i,mm){
      int s,k;
      cin>>s>>k;
      lp(j,k){
	int x;
	cin>>x;
	m[x]+=s;
	if(k==1){
	  a[x]+=s;
	}
      }
    }
    int ansmax=-INF,es,ansmin=INF;
    lp(i,n){
      if(ansmax<m[i+1]) es=i;
      ansmax=max(ansmax,m[i+1]);
    }
    lp(i,n){
      if(i==es) continue;
      ansmin=min(ansmin,a[i+1]);
    }
    //  cout<<ansmax<<" "<<ansmin<<endl;
    cout<<ansmax-ansmin+1<<endl;
  }
  return 0;
}



Measured memory_bytes: 3236
#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
  
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
  
const ll MOD=1e9+7;
const ll INF=1e18;
  
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
 
int d[100][100];
int sum[100];
 
int main(){
    int n;
 
    while(1){
 
        cin >> n;
        if(n == 0)break;
        char tmp[100];
        for(int i = 0;i < n;i++){
            cin >> tmp;
            sum[i] = 0;
            for(int j = 0;j < strlen(tmp);j++){
                if(tmp[j] == '.'){
                    d[i][j] = -1;
                    sum[i] = j+1;
                }else if(tmp[j] == '+'){
                    d[i][j] = -2;
                    break;
                }else if(tmp[j] == '*'){
                    d[i][j] = -3;
                    break;
                }else{
                    d[i][j] = tmp[j] - '0';
                }
            }
        }
        while(n != 1){
            /*
            cout << "+++++" << endl;
            for(int i = 0;i < n;i++){
                for(int j = 0;j < sum[i]+1;j++){
                    cout << d[i][j] ;
                }
                cout << endl;
            }
*/
 
            int maxlen = 0,o = -1;
            for(int i = 0;i < n;i++){
                if(sum[i] > maxlen){
                    o = i;
                    maxlen = sum[i];
                }
            }
            int count = 1,ans = d[o][maxlen];
            for(int i = o+1;i < n;i++){
                if(maxlen == sum[i]){
                    count++;
                    if(d[o-1][maxlen-1] == -2){
                        ans += d[i][maxlen];
                    }else{
                        ans *= d[i][maxlen];
                    }
                }else{
                    break;
                }
            }
            d[o-1][maxlen-1] = ans;
            for(int i = o + count;i < n;i++){
                for(int j = 0;j <= sum[i];j++){
                    d[i-count][j] = d[i][j];
                }
            }
            for(int i = o+count;i < n;i++) sum[i-count] = sum[i];
            n -= count;
        }
        cout << d[0][0] << endl;
 
 
    }
}


Measured memory_bytes: 3024
from heapq import heappop,heappush
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            D = [[False]*W for i in range(H)]
            Q = [(0,(h,w))]
            while Q:
                q = heappop(Q)
                qh,qw = q[1][0],q[1][1]
                if qh<0 or qh>=H or qw<0 or qw>=W:continue
                if S[qh][qw]=="#":continue
                if D[qh][qw]:continue
                D[qh][qw]=True
                ans = max(q[0],ans)
                heappush(Q,(q[0]+1,(qh+1,qw)))
                heappush(Q,(q[0]+1,(qh-1,qw)))
                heappush(Q,(q[0]+1,(qh,qw+1)))
                heappush(Q,(q[0]+1,(qh,qw-1)))
print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define lp(i, n) for (int i = 0; i < (n) ; ++i)
#define pr1(x) cout<<"[" << #x << ": " << x << "] \n";
#define pr2(x, y) cout<<"[" << #x << ": " << x <<", "<< #y << ": " << y <<"] \n";
#define mod 1000000007
#define int long long
#define sz(v) (int)(v).size()

void solve() {
        int n; cin >> n;
        string str; cin >> str;

        vector<int> w, r;
        int an= 0, j= n- 1;
        for (int i = 0; i< n; i++) {
                if (str[i]== 'W') {
                        while (j> i&& str[j]=='W') {
                                j--;
                        }
                        if (j> i) {
                                swap(str[i], str[j]);
                                an++;
                        }
                }

        }
        cout << an<< "\n";
}

int32_t main(){
ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
        int t = 1;
        //cin >> t;
        while ( t-- ) {
                solve();
        }
return 0;
}


Measured memory_bytes: 3744
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        vector<int> up(n+1, 0), down(n+1, 0);
        for(;;){
            int a, b;
            cin >> a >> b;
            if(a == 0)
                break;

            // aÆbª¯¶ÈçÎ½àµÈ¢
            if(a == b)
                continue;

            // að°ÉÚ®³¹éêAaª·ÅÉ°ÌãÉ êÎ½àµÈ¢
            if(b == 0 && down[a] == 0)
                continue;

            // aªbæèãÈçÎ½àµÈ¢
            if(b != 0){
                int c = a;
                bool ignore = false;
                while(c != 0){
                    if(c == b)
                        ignore = true;
                    c = down[c];
                }
                if(ignore)
                    continue;
            }

            // aæèãÌubNð°Ö~ë·
            int c = a;
            while(c != 0){
                down[c] = up[down[c]] = 0;
                c = up[c];
            }

            // bÌÅàãÌubNÉaðæ¹é
            if(b != 0){
                c = b;
                while(up[c] != 0)
                    c = up[c];
                up[c] = a;
                down[a] = c;
            }
        }

        vector<int> ret;
        for(int i=1; i<=n; ++i){
            if(down[i] != 0)
                continue;
            int j = i;
            int k = 0;
            while(j != 0){
                ++ k;
                j = up[j];
            }
            ret.push_back(k);
        }
        sort(ret.begin(), ret.end());

        for(unsigned i=0; i<ret.size(); ++i)
            cout << ret[i] << endl;
        cout << "end" << endl;
    }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define lld long long int
#define M 1000000007
#define fors(i,n) for(int i=0;i<n;++i)
#define fore(i,a,b) for(int i=a;i<=b;++i)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define vv vector<int>
#define endl "\n"
#define test(i) cout<<i<<endl
#define itrt int t; cin>>t; fors(i,t)
#define itr1 int t; cin>>t;
#define ff first
#define ss second
#define pb push_back
#define vmp make_pair
#define ppb pop_back
#define sorta(a,n) sort(arr,arr+n)
#define sortv(x) sort(x.begin(),x.end())
void file(){
    #ifdef LOCAL
    freopen("demo.in","r",stdin);
    freopen("demo.out","w",stdout);
    #endif
}
int main(){
    fastio;
    file();
    long long a,b;
    cin>>a>>b;
    if(a==1 || b==1){
        test("1");
    }
    else{
        test((a*b+1)/2);
    }
}

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

int main(){
  int N, K;
  cin >> N >> K;
  
  int ans = 0;
  for (int i = 0; i < N; i++){
    int X;
    cin >> X;
    
    if (X <= K / 2){
      ans += X * 2;
    }
    else{
      ans += (K - X) * 2;
    }
    
  }
  
  cout << ans << endl;
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(X, i) ((X>>i)&1)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define r_all(a) (a).rbegin(), (a).rend()
#define in(x) cin>>x
#define ina(x, n) rep(x_i,n) cin>>x[x_i]
#define outa(x, n) rep(x_i,n) cout<<x[x_i]<<" \n"[x_i==n-1]

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vll;
typedef priority_queue<ll> pq;

const int MOD = 1e9+7;
const int INF = (1<<30);
const ll INFL = (1L<<62);

int main() {
  int n; in(n);
  vl p(n), q(n); ina(p,n);
  rep(i,n) {
    q[p[i]-1] = i;
  }
  int t = 1, ans = 1;
  REP(i,1,n) {
    if (q[i] > q[i-1]) t++;
    else t = 1;
    ans = max(ans, t);
  }
  cout << n - ans << endl;
  return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb(x) push_back(x)

typedef pair<ll,ll> pp;
int lcm(int a, int b)
{
    int lar = max(a, b);
    int small = min(a, b);
    for (int i = lar; ; i += lar) {
        if (i % small == 0)
            return i;
    }
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

bool sortbysec(const pair<ll,ll> &a, const pair<ll,ll> &b) {
    return (a.second < b.second);
}

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

ll lis( ll arr[], ll n )
{
    ll lis[n];
   
    lis[0] = 1;
  
    /* Compute optimized LIS values in bottom up manner */
    for (ll i = 1; i < n; i++)
    {
        lis[i] = 1;
        for (ll j = 0; j < i; j++ )
            if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
                lis[i] = lis[j] + 1;
    }
  
    // Return maximum value in lis[]
    return *max_element(lis, lis+n);
}

void solve(){
    ll a, b , c , d;
    cin >> a >> b >> c >> d;
    ll x, y;
    if(a%d == 0) y = a/d;
    else y = a/d+1;
    if(c%b == 0) x = c/b;
    else x = c/b+1;
    //cout << x << " " << y << endl;
    if(x <= y) cout << "Yes\n";
    else cout << "No\n";
}

int main()
{
    //ll t; cin >> t; while(t--)
        solve();
}


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

using namespace std;
typedef long long ll;

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, m, n) for (ll i = (m); i < (n); i++)
#define FORR(i, m, n) for (ll i = (m); i >= (n); i--)
#define INF 1e9
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl

int main(int argc, char const *argv[])
{
    ll a, b;
    cin >> a >> b;
    ll res = 0;
    if (b > 1)
    {
        FOR(i, 1, (b + 1))
        {
            if (a + (i - 1) * (a - 1) >= b)
            {
                res = i;
                break;
            }
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

ll N, Q;
ll W[100000], U[100000], V[100000], A[100000], B[100000];
vector<ll> E[100000];
ll x[100000][3], y[100000];
ll depth[100000], parent[20][100000], mx[20][100000];

void dfs(ll v, ll p, ll d) {
  parent[0][v] = p;
  depth[v] = d;
  for(ll u : E[v]) if(u != p) dfs(u, v, d + 1);
}

ll subtree_size(ll v, ll p) {
  vector<ll> child;
  for(ll u : E[v]) if(u != p) child.push_back(subtree_size(u, v));
  sort(child.begin(), child.end(), greater<ll>());
  REP(i, 0, 3) x[v][i] = i < child.size() ? child[i] : 0;
  for(ll u : E[v]) if(u != p) mx[0][u] = x[v][0] != y[u] ? x[v][0] : x[v][1];
  y[v] = W[v];
  REP(i, 0, child.size()) y[v] += child[i];
  return y[v];
}

ll query(ll u, ll v) {
  if(depth[u] > depth[v]) swap(u, v);
  REP(i, 0, 20) if(((depth[v] - depth[u]) >> i) & 1) v = parent[i][v];
  if(u == v) return u;
  for(ll i = 19; i >= 0; i--) if(parent[i][u] != parent[i][v]) {
    u = parent[i][u];
    v = parent[i][v];
  }
  return parent[0][u];
}

int main(void) {
  cin >> N;
  REP(i, 0, N) cin >> W[i];
  REP(i, 0, N - 1) {
    cin >> U[i] >> V[i]; U[i]--; V[i]--;
    E[U[i]].push_back(V[i]);
    E[V[i]].push_back(U[i]);
  }
  cin >> Q;
  REP(i, 0, Q) { cin >> A[i] >> B[i]; A[i]--; B[i]--; }

  dfs(0, -1, 0);
  subtree_size(0, -1);
  REP(i, 0, 19) REP(j, 0, N) parent[i + 1][j] = parent[i][j] >= 0 ? parent[i][parent[i][j]] : -1;
  REP(i, 0, 19) REP(j, 0, N) if(parent[i][j] >= 0) mx[i + 1][j] = max(mx[i][j], mx[i][parent[i][j]]);

  REP(q, 0, Q) {
    ll a = A[q], b = B[q], lca = query(a, b);
    ll ans = 0;
    if(lca == a || lca == b) {
      if(lca == b) swap(a, b);
      ans = max(ans, x[b][0]);
      for(ll i = 19; i >= 0; i--) {
        if(parent[i][b] >= 0 && depth[parent[i][b]] >= depth[lca]) {
          ans = max(ans, mx[i][b]);
          b = parent[i][b];
        }
      }
      ans = max(ans, y[0] - y[lca]);
    } else {
      ans = max(ans, x[a][0]);
      ans = max(ans, x[b][0]);
      for(ll i = 19; i >= 0; i--) {
        if(parent[i][a] >= 0 && depth[parent[i][a]] > depth[lca]) {
          ans = max(ans, mx[i][a]);
          a = parent[i][a];
        }
      }
      for(ll i = 19; i >= 0; i--) {
        if(parent[i][b] >= 0 && depth[parent[i][b]] > depth[lca]) {
          ans = max(ans, mx[i][b]);
          b = parent[i][b];
        }
      }
      vector<ll> r;
      r.push_back(y[a]);
      r.push_back(y[b]);
      r.push_back(-1);
      sort(r.begin(), r.end(), greater<ll>());
      REP(i, 0, 3) if(r[i] != x[lca][i]) ans = max(ans, x[lca][i]);
      ans = max(ans, y[0] - y[lca]);
    }
    cout << ans << endl;
  }
}



Measured memory_bytes: 37312
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int NMAX =100000;
struct muchie
{
    int nod, index;
};
vector <muchie>G[NMAX+5];
/*struct muchie{
    int nod1, nod2, color;
};*/
int culori[NMAX+5];
int viz[NMAX+5];

  int nr_muchii=0;
void dfs(int nod, int culoare)
{
    viz[nod] =1;
    for(int i=0;i<G[nod].size();i++)
    {
       if(viz[G[nod][i].nod]==0)
       {
           culoare ++;
            if(culoare>nr_muchii)
             culoare = 1;
           dfs(G[nod][i].nod, culoare);
           culori[G[nod][i].index] = culoare;
       }
    }

}
int main()
{
    int n, x, y, i;
    cin>>n;
    muchie aux;
    int index =0;
    for(i=1;i<n;i++)
    {
        cin>>x>>y;
        aux.nod=y;
        aux.index =index;
        G[x].push_back(aux);
        aux.nod = x;
        G[y].push_back(aux);
        index++;
    }

    int start =0;
    for(i=1;i<=n;i++)
    {
       if(nr_muchii<G[i].size())
       {
           nr_muchii = G[i].size();
           start = i;
       }
    }
    cout<<nr_muchii<<"\n";
    dfs(start, 0);
    for(i=0;i<n-1;i++)
      cout<<culori[i]<<"\n";

}



Measured memory_bytes: 7680
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		
		int k=sc.nextInt();
		int a=sc.nextInt();
		int b=sc.nextInt();
		
		int c=k;
		int flag=0;
		
		while(c<=b){
			
			if(a<=c && c<=b){
				System.out.println("OK");
				System.exit(0);
				
			}
			c+=k;
			
		}
		//System.out.println(c);
		System.out.println("NG");
		
		

		
	}
	
}


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

int main() {
  int n,m;
  cin >> n >> m;
  vector<pair<ll,ll>> ab(n);
  for (int i=0; i<n; i++) {
    scanf("%d %d",&ab[i].first,&ab[i].second);
  }
  sort(ab.begin(),ab.end());

  ll ans=0;
  for (int i=0;; i++) {
    if (ab[i].second<m) {
      ans+=ab[i].second*ab[i].first;
      m-=ab[i].second;
    }
    else {
      ans+=m*ab[i].first;
      break;
    }
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
#define int long long
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
 
void accell() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
}
const int N = 3e5;
int dp[N][3];
 
signed main() {
    accell();
    int n, k;
    int r, s, p;
    cin >> n >> k;
    cin >> r >> s >> p;
    string a;
    cin >> a;
    for (int i = 0; i < a.size(); ++i) {
        if (i - k < 0) {
            if (a[i] == 's') {
                dp[i][0] = r;
            }
            if (a[i] == 'p') {
                dp[i][1] = s;
            }
            if (a[i] == 'r') {
                dp[i][2] = p;
            }
        }
        if (i - k >= 0) {
            if (a[i] == 's') {
                dp[i][0] = max(dp[i - k][1], dp[i - k][2]) + r;
                dp[i][1] = max(dp[i - k][0], dp[i - k][2]);
                dp[i][2] = max(dp[i - k][0], dp[i - k][1]);
            }
            if (a[i] == 'p') {
                dp[i][0] = max(dp[i - k][1], dp[i - k][2]);
                dp[i][2] = max(dp[i - k][0], dp[i - k][1]);
                dp[i][1] = max(dp[i - k][0], dp[i - k][2]) + s;
            }
            if (a[i] == 'r') {
                dp[i][2] = max(dp[i - k][0], dp[i - k][1]) + p;
                dp[i][1] = max(dp[i - k][0], dp[i - k][2]);
                dp[i][0] = max(dp[i - k][1], dp[i - k][2]);
            }
        }
    }
    int res = 0;
    for (int i = n - 1; i >= max(n - k, 0LL); --i) {
        res += max(max(dp[i][1], dp[i][0]), dp[i][2]);
        // cout << max(max(dp[i][1], dp[i][0]), dp[i][2]) << ' ';
    }
    cout << res << '\n';
    return 0;
}


Measured memory_bytes: 4588
#include <stdio.h>

typedef struct {
    int state[2][7];
    int assign[7];
    int p; // 次に代入すべきインデックス
} dice;

dice d;
int rot[6][7] = {
    {0,1,2,3,4,5,6},
    {0,2,6,3,4,1,5},
    {0,4,2,1,6,5,3},
    {0,3,2,6,1,5,4},
    {0,5,1,3,4,6,2},
    {0,1,3,5,2,4,6},
};
int tr['Z'];

void dice_init(dice *d, int *a) {
    int i;
    int t[6] = {0, 'N', 'E', 'W', 'S', 'L'};
    for (i = 1; i <= 6; i++) d->assign[i] = a[i];
    for (i = 1; i <= 5; i++) tr[t[i]] = i;
    for (i = 1; i <= 6; i++) d->state[0][i] = rot[0][i];
    d->p = 1;
}

void dice_rotate(dice *d, char dir) {
    int i;
    for (i = 1; i <= 6; i++) {
        d->state[d->p][i] = d->state[!(d->p)][rot[tr[dir]][i]];
    }
    d->p = !(d->p);
    // printf("rotate %c: ", dir);
    // for (i = 1; i <= 6; i++) printf("%d ", d->state[!(d->p)][i]);
    // printf("\n");
}

void set_top(dice *d, int t) {
    char s[] = "NEEEN";
    char *ps = s;
    // printf("%c\n", *ps);
    while (*ps) {
        if (d->assign[d->state[!(d->p)][1]] == t) return;
        dice_rotate(d, *ps);
        ps++;
    }
}

void set_front(dice *d, int f) {
    while (d->assign[d->state[!(d->p)][2]] != f) dice_rotate(d, 'L');
}

int query[25][2];
int q;
int main(void) {
    int i;
    int a[7];
    for (i = 1; i <= 6; i++) scanf("%d", a + i);
    scanf("%d", &q);
    for (i = 1; i <= q; i++) scanf("%d%d", query[i], query[i] + 1);
    dice_init(&d, a);
    for (i = 1; i <= q; i++) {
        set_top(&d, query[i][0]);
        // printf("%d\n", d.assign[d.state[!(d.p)][1]]);
        set_front(&d, query[i][1]);
        // printf("%d\n", d.assign[d.state[!(d.p)][2]]);
        printf("%d\n", d.assign[d.state[!(d.p)][3]]);
    }
    return 0;
}


Measured memory_bytes: 2060
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>


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

const long long MAX = 5100000;
const long long INF = 1LL << 60;
const long long MOD = 1'000'000'007LL;
const long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main()
{
	/*
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	*/
	ll N; scanf("%lld", &N);
	vector<ll> a(N); for (ll i = 0; i < N; i++) scanf("%lld", &a[i]);
	a.push_back(-1);
	ll res = 0;
	for (ll i = 0; i < N; i++) {
		if (a[i] >= a[i + 1]) {
			res++;
		}
	}
	cout << res << "\n";
	cout << N << "\n";
	return 0;

}



Measured memory_bytes: 4448