akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
import sys
N=input()
bit=[ [ 0 for _ in range(N+1) ] for __ in range(27) ] 

def add(i,a,w):
    while a<=N:
        bit[i][a]+=w
        a+=a&-a

def sum(i,a):
    ret=0
    while 0<a:
        ret+=bit[i][a]
        a-=a&-a
    return ret

S=sys.stdin.readline().strip()
S=[None]+list(S) #1-indexed
for j,x in enumerate(S):
    if j==0: continue
    i=ord(x)-96
    add(i,j,1)

Q=input()
for _ in range(Q):
    q1,q2,q3=sys.stdin.readline().split()
    if q1=="1":
        q1=int(q1)
        q2=int(q2)
        current_s=q3
        former_s=S[q2]
        former_s=ord(former_s)-96  #1-indexed
        S[q2]=current_s         #文字列で更新された1文字を置き換える
        current_s=ord(current_s)-96
        add(current_s,q2,1)
        add(former_s,q2,-1) 
    if q1=="2":
        q2=int(q2)
        q3=int(q3)
        begin,end=q2,q3
        cnt=0
        for i in range(1,27):
            if 0<sum(i,end)-sum(i,begin-1):
                cnt+=1
        print cnt

Measured memory_bytes: 183788
package main

import (
	"io"
	"os"

	"fmt"
)

func Solve(in io.Reader, out io.Writer) {
	var n int
	fmt.Fscan(in, &n)

	a := make([]int64, n)
	amap := make(map[int64]int, n)

	var sum int64
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &a[i])
		sum += a[i]
		amap[sum]++
	}
	var cnt int
	for _, v := range amap {
		if v <= 1 {
			continue
		}
		for j := v - 1; j > 0; j-- {
			cnt += j
		}
	}
	cnt += amap[0]

	fmt.Fprintln(out, cnt)
}

func main() {
	Solve(os.Stdin, os.Stdout)
}


Measured memory_bytes: 12544
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
  for(;;){
    int n;
    cin >> n;
    if(n==0) break;
    vector<int> v(n);
    for(int i=0;i<n;i++){
      cin >> v[i];
    }
    sort(v.begin(),v.end());
    long long ret = 0;
    for(int i=0; i<n-1; i++){
      ret += v[i] * (n-1-i);
    }
    cout << ret << endl;
  }
  return 0;
}

Measured memory_bytes: 1248
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int inf=2147483647,dx[]={-1,0,1,0},dy[]={0,-1,0,1};// 上 左 下 右
const int N=100005,M=1000005,mod=1000000007;
const long long llinf=9223372036854775807ll;
long long a,b;
long long f(long long x)
{
	if(x%4==0)
		return x;
	if(x%4==1)
		return 1;
	if(x%4==2)
		return x+1;
	return 0;
}
int main(){
	cin>>a>>b;
	cout<<(f(b)^((a==0)?0:f(a-1)));
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using s32 = int32_t;
using u32 = uint32_t;
using s64 = int64_t;
using u64 = uint64_t;

int main() {
	u32 N, M;
	cin >> N >> M;
	
	u64 ansN = N * (N - 1) / 2;
	u64 ansM = M * (M - 1) / 2;
	
	cout << ansN + ansM;
	
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache
import heapq

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3,d + 1,2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7

def main():
    N,A = cin.mapInt()
    X = cin.mapInt()
    dp = [[[0 for k in range(3000)] for j in range(51)]  for i in range(51)]
    dp[0][0][0] = 1
    ans = 0
    for i in range(N):
        for j in range(i + 1):
            for k in range(2500):
                dp[i + 1][j][k] += dp[i][j][k]  
                dp[i + 1][j + 1][k + X[i]] += dp[i][j][k]
    for j in range(1,N + 1):
        ans += dp[N][j][j * A]
    print(ans)
    return

if __name__ == "__main__":
    main()


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

using namespace std;
typedef long long LL;

const int N=2e5+10;

int n,L,T,pos[N],w[N],ans[N];

void Init()
{
	scanf("%d%d%d",&n,&L,&T);
	for (int i=0;i<n;++i) 
	{
		scanf("%d%d",&pos[i],&w[i]);
		if (w[i]==2) w[i]=-1;
	}
}
void Solve()
{
	LL cg=0;
	for (int i=0;i<n;++i)
	{
		LL epos=pos[i]+1ll*w[i]*T;
		if (epos<0) cg-=(-(epos+1)/L)+1;
		else cg+=epos/L;
		ans[i]=(epos%L+L)%L;
		cg%=n;
	}
	sort(ans,ans+n);
	for (int i=0;i<n;++i) printf("%d\n",ans[(i+cg+n)%n]);
}

int main()
{
	Init();
	Solve();
	return 0;
}

Measured memory_bytes: 2432
import sys

ary=[]
ans=[]
def solve(a,b,c,d,e,f):
    if c*e-b*f==0:
        x=0
    else:
        x=(c*e-b*f)/(a*e-b*d)
    if c*d-a*f==0:
        y=0
    else:
        y=(c*d-a*f)/(b*d-a*e)
    return [x,y]

for i in sys.stdin:
    ary.append(list(map(int,i.split())))
    ans.append(solve(*ary[-1]))

for i in range(len(ans)):
    print('{0:.3f} {1:.3f}'.format(round(ans[i][0],3),round(ans[i][1],3)))

Measured memory_bytes: 7640
s=list(input())
t=list(input())
n=len(t)
val=0
for i in range(len(s)-n+1):
    temp=0
    for j in range(n):
        if s[i+j]==t[j]:
            temp+=1
    val=max(val,temp)
    if val==n:
        break
print(n-val)

Measured memory_bytes: 65052
#include <stdio.h>
#include<stdlib.h>
int asc(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}
int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    k--;
    int i;
    int h[100005];
    for (i = 0; i < n; i++)
        scanf("%d", &h[i]);
    qsort(h, n, sizeof(int), asc);
    int ans = h[n - 1];
    for (i = 0; i < n - k; i++)
        if (ans > h[i + k] - h[i])
            ans = h[i + k] - h[i];
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
int n,m;
char chair[200];

void A(char ch){
  int i=1;
  while(chair[i]!='#') i++;
  chair[i]=ch;
}

void B(){
  int i=n;
  while(chair[i]!='#')i--;
  chair[i]='B';
}

void C(int kai){
  if(kai==0){
    if(n%2)chair[(n+1)/2]='C';
    else chair[n/2+1]='C';
    return;
  }

  int i=0;
  for(i=1;i<=n;i++){
    if(chair[i]=='#')continue;
    if(chair[i+1]=='#') chair[i+1]='C',i=n+2;
    else if(chair[i-1]=='#') chair[i-1]='C',i=n+2;
   
  }
  assert(i!=n+2);
}

void D(){
  int R=0,L=0;
  while(chair[n-R]=='#')R++;
  while(chair[L+1]=='#')L++;
  
  int M=0,idx=0,cnt=0;
  for(int i=1;i<=n;i++){
    if(chair[i]=='#')cnt++;
    else cnt=0;
    if(M+M%2<cnt) M=cnt,idx=i;
  }
  if(M<=2&&L<=1&&R<=1) A('D');
  else if(L-1>=(M-1)/2&&L-1>=R-1)chair[1]='D';
  else if(R-1>(M-1)/2)chair[n]='D';
  else chair[(idx-M+1)+(M-1)/2]='D';

}

int main(){
  while(1){
    cin>>n>>m;
    if(!n&&!m)break;
    memset(chair,'#',sizeof(chair));
    chair[0]=chair[n+1]=0;
    for(int i=0;i<m;i++){
      char a;
      cin>>a;
      if(a=='A') A(a);
      if(a=='B') B();
      if(a=='C') C(i);
      if(a=='D') D();
    }
    printf("%s\n",chair+1);
  }
  return 0;
}

Measured memory_bytes: 1120
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define mod 1000000007
int dis[1010][1010],cnt[1010][1010]; 
char a[1010][1010];
bool vis[1010][1010];
int mark[4][2];
struct node{
	int x,y;
};
int h,w;
void spafa(){
	queue<node>q;
	vis[1][1]=1;
	dis[1][1]=0;cnt[1][1]=1;
	q.push(node{1,1});
	while(!q.empty()){
		node t=q.front();q.pop();
		int x=t.x,y=t.y;
		vis[x][y]=0;
		for(int i=0;i<2;i++){
			int xx=x+mark[i][0],yy=y+mark[i][1];
			if(a[xx][yy]=='#')continue;
			if(dis[xx][yy]>dis[x][y]+1){
				dis[xx][yy]=dis[x][y]+1,cnt[xx][yy]=cnt[x][y];
				if(!vis[xx][yy])vis[xx][yy]=1,q.push(node{xx,yy});
			}
			else
			if(dis[xx][yy]==dis[x][y]+1){
				(cnt[xx][yy]+=cnt[x][y])%=mod;
				if(!vis[xx][yy])vis[xx][yy]=1,q.push(node{xx,yy});
			}
		}
	}
}
int main(){
	mark[0][0]=1,mark[1][1]=1;
	scanf("%d%d",&h,&w);
	for(int i=1;i<=h;i++)scanf("%s",a[i]+1);
	for(int i=1;i<=w;i++)a[0][i]=a[h+1][i]='#';
	for(int i=1;i<=h;i++)a[i][0]=a[i][w+1]='#';
	memset(dis,0x3f,sizeof(dis));
	spafa();
	printf("%d",cnt[h][w]);
}

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

int main() {
  int c,a,b;
  cin>>c>>a>>b;
  if (1<=c<=20,1<=a<=100,1<=b<=2000){
    if (a*c<=b){
      cout<<a*c<<endl;
      }
    else {
      cout<<b<<endl;
      }
    }
  }
  

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;

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

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

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

    int h1, m1, h2, m2, k; cin>>h1>>m1>>h2>>m2>>k;

    int st = h1 * 60 + m1;
    int en = h2 * 60 + m2;

    cout << (en - st - k) << endl;

    return 0;
}

Measured memory_bytes: 3608
#include <stdio.h>

void printLine(int *A, int N)
{
    int i;

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

void swap(int *a, int *b)
{
    int tmp;

    tmp = *a;
    *a = *b;
    *b = tmp;
}

int bubbleSort(int *A, int N)
{
    int sw = 0;
    int flag = 1;
    for (int i = 0; flag; i++) {
        flag = 0;
        for (int j = N - 1; j > i; j--) {
            if (A[j - 1] > A[j]) {
                swap(&A[j], &A[j - 1]);
                sw++;
                flag = 1;
            }
        }
    }
    return sw;
}

int main()
{
    int N, A[100], sw;

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

    sw = bubbleSort(A, N);
    printLine(A, N);
    printf("%d\n", sw);

    return 0;
}


Measured memory_bytes: 2664
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using ll = int64_t;
using ld = long double;
using ull = uint64_t;
using namespace std;
using namespace __gnu_pbds;
typedef vector <int> vi;
typedef pair <int, int> ii;

const int INF = (int)1e9;

#define maxn 100010



int main() {
#ifdef BZ
    freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(6);

    int n, m, q;
    cin >> n >> m >> q;

    vector <vi> a(n + 1);

    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        a[u].push_back(v);
    }

    map <int, int> f;

    vector <vi> ans(n + 1, vi (n + 1));

    for(int i = 1; i <= n; i++) {
        f.clear();
        int v = 0;
        for(int j = i; j <= n; j++) {
            for(auto el: a[j]) {
                if(f.count(el)) f[el]++;
                else f[el] = 1;
            }
            if(!f.empty() and f.begin() -> first == j) {
                v += f.begin() -> second;
                f.erase(f.begin());
            }
            ans[i][j] = v;
        }
    }

    for(int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        cout << ans[u][v] << "\n";
    }

}

Measured memory_bytes: 3200
import collections

n, k = map(int, input().split())
a = [int(_) for _ in input().split()]

num = len(set(a))
if num <= k:
    print(0)
else:
    num = num - k
    c = collections.Counter(a).most_common()
    ans = 0
    for i in reversed(c):
        if num > 0:
            ans += i[1]
        else:
            break
        num -= 1
    print(ans)

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

int main(){
  long long int N,suma=0,sumb=0,sums=0,kazu=0;
  cin>>N;
  vector<long long int> A(N);
  vector<long long int> B(N);
  vector<long long int> S(N);
  for(long long int i=0;i<N;i++){
    cin>>A.at(i);
    suma+=A.at(i);
  }
  for(long long int i=0;i<N;i++){
    cin>>B.at(i);
    sumb+=B.at(i);
    S.at(i)=A.at(i)-B.at(i);
    if(S.at(i)<0){
      sums+=S.at(i);
      kazu++;
    }
  }
  if(suma<sumb){
    cout<<-1<<endl;
    return 0;
  }
  if(kazu==0){
    cout<<0<<endl;
    return 0;
  }
  sort(S.begin(),S.end());
  reverse(S.begin(),S.end());
  long long int sum=0;
  for(long long int i=0;i<N;i++){
    sum+=S.at(i);
    if(sum+sums>=0){
      cout<<kazu+i+1<<endl;
      return 0;
    }
  }
  
  
  
}

Measured memory_bytes: 2560
#include <iostream>
#include <string>
using namespace std;
 
int main() {
    int a, b;
	cin >> a >> b;
	int c = atoi((to_string(a)+to_string(b)).c_str());
  	for(int i=1;i*i<=c;i++){
      if(i*i==c){
        cout << "Yes" << endl;
        return 0;
      }
    }
  	cout <<"No" << endl;
  	return 0;
}

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

#define Speed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define mod 1000000007
#define fr first
#define sc second
#define pb push_back
#define PI acos(-1.0)
#define print(num,ans) cout<<setprecision(num)<<fixed<<ans
#define ordered_set tree<pair<int,int> , null_type,less<pair<int,int> >, rb_tree_tag,tree_order_statistics_node_update>


int main()
{
    Speed;
    int x,y;
    cin>>x>>y;
    ll sum = 1;
    if(y == 1)return cout<<0 , 0;
    for(int i=1;;i++)
    {
        sum+= x;
        sum--;
        if(sum >= y)return cout<<i , 0;
    }


    return 0;
}



Measured memory_bytes: 256
#include<cstdio>

int a,d,n;
int prime[1000000];
int main(void){
	prime[1]=1;
	for(int i=2;i<=1000000;i++){
		if(prime[i]==0){
			for(int j=i*2;j<=1000000;j+=i)prime[j]=1;
		}
	}
	while(1){
		scanf("%d %d %d",&a,&d,&n);
		if(a+d+n==0)break;
		int cnt=0;
		while(1){
			if(prime[a]==0)cnt++;
			if(cnt==n)break;
			a+=d;
		}
		printf("%d\n",a);
	}
	return 0;
}

Measured memory_bytes: 4932
#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

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

#define sz(s) (int)(s.size())
#define all(s) s.begin(), s.end()
#define rep(a, b, c) for(int a = b; a <= c; ++a)
#define per(a, b, c) for(int a = b; a >= c; --a)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
//using namespace __gnu_pbds;

typedef unsigned long long ull;
typedef long long ll;
/*typedef tree<pair<int, int>, 
null_type, less<pair<int, int>>, 
rb_tree_tag, tree_order_statistics_node_update>
ordered_set;*/
//find_by_order() order_of_key()

const double eps = 1e-7;
const int mod = 1e9+7, MXN = 5e5+17;
const int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};

template<typename T>inline bool updmin(T &a, const T &b) {return a > b ? a = b,1 : 0;}
template<typename T>inline bool updmax(T &a, const T &b) {return a < b ? a = b,1 : 0;}

int32_t main() { _
#ifdef DanQQQQQ
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	string s; cin >> s;
	vector<char>v;
	for(auto&to:s) {
		if(to == 'B' && !v.empty()) v.pop_back();
		if(to != 'B') v.push_back(to);
	}
	for(auto&to:v) cout << to;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
using ll=long long;
using P=pair<ll,ll>;
using PP=tuple<ll,ll,ll>;
using S=multiset<ll>;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
void decimal(int x){cout<<fixed<<setprecision(x);}
//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/GCD(a,b))*GCD(a,b);}
ll POW(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*POW(a,b-1)%mod;ll k=POW(a,b/2);return k*k%mod;}
vi calc(ll x){vi res;while(x>0){res.eb(x%10);x/=10;}reverse(all(res));return res;}

void solve() {
  string s,t;
  cin>>s>>t;
  string s_=s;
  bool f=false;
  rep(i,26){
    s_+='a'+i;
    if(s_==t) f=true;
    s_=s;
  }
  YesNo(f);
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<pair<int, int> > > g;
vector<int> color;
bool v[111001];
void col(int n) {
   queue<int> q;
   int c = 0;
   set<int> vertex_colored;
   if(v[n])
      return;
      v[n] = 1;
   for(i = 0;i<g[n].size();i++) {
      if(color[g[n][i].second]!=-1) {
         vertex_colored.insert(color[g[n][i].second]);
      }
   }
   for(i = 0;i<g[n].size();i++) {
      if(!v[g[n][i].first]) {
         q.push(g[n][i].first);
      }
      if(color[g[n][i].second]==-1) {
         while(vertex_colored.find(c)!=vertex_colored.end())
            c++;
            color[g[n][i].second] = c;
            vertex_colored.insert(c);
            c++;
      }
   }
   while(!q.empty()) {
      int temp = q.front();
      q.pop();
      col(temp);
   }
   return;
}
int main() {
   int u,w;
   set<int> empty;
   //cout<<"Enter number of vertices and edges respectively:";
   cin>>n;
   //cout<<"\n";
   g.resize(n); //number of vertices
   color.resize(n-1,-1); //number of edges
   memset(v,0,sizeof(v));
   for(i = 0;i<n-1;i++) {
      //cout<<"\nEnter edge vertices of edge "<<i+1<<" :"<<"\n";
      cin>>u>>w;
      u--; w--;
      g[u].push_back(make_pair(w,i));
      g[w].push_back(make_pair(u,i));
   }
   col(0);
   set<int> ans;
   for(i = 0;i<n-1;i++) {
      ans.insert(color[i]+1);
   }
   cout<<ans.size()<<'\n';
   for(i = 0;i<n-1;i++) {
      cout<<color[i]+1<<'\n';
   }
}


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

const ll mod = 1e9 + 7;

int main() {
  ll n, a, b, p;
  cin >> n >> a >> b;
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (i) {
      ans += min((x - p) * a, b);
    }
    p = x;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3604
use std::str::FromStr;
use std::fmt::Debug;

fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let d: u32 = read_as_vec()[0];
    if d == 25{
        println!("Christmas");
    }else if d == 24{
        println!("Christmas Eve");
    }else if d == 23{
        println!("Christmas Eve Eve");
    }else{
        println!("Christmas Eve Eve Eve");
    }
 }

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll zero = 0;
const ll INF = 10000000000000000; //10^16
const ll MOD = 1000000007; //10^9+7

int main() {
    ll N;
    cin >> N;
    vector<ll> a(N);
    vector<ll> cnt(N+2, zero);
    for(int i = 0; i < N; i++){
        cin >> a.at(i);
    }
    
    for(int i = 0; i < N; i++){
        cnt.at(a.at(i))++;
    }
    
    ll tmpans = 0;
    for(int i = 0; i < N+2; i++){
        tmpans += cnt.at(i)*(cnt.at(i)-1)/2;
    }
    
    ll ans;
    for(int k = 1; k <= N; k++){
        ans = tmpans;
        ans -= cnt.at(a.at(k-1))-1;
        printf("%lld\n", ans);
    }
}

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

using namespace std;

int main() {
    int K, N;
    cin >> K >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    vector<int> v;
    v.push_back(K - A[N - 1] + A[0]);
    for(int i = 1; i < N; i++) {
        v.push_back(A[i] - A[i - 1]);
    }
    int m = *max_element(v.begin(), v.end());
    int ans = K - m;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2168
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto s = readln.split.map!(to!int);
    auto H = s[0];
    auto W = s[1];
    auto D = s[2];

    auto N = max(H, W) * 3;
    auto B = new int[][](N, N);

    for (int i = 0; i < N; i += D) {
        for (int j = 0; j < N; j += D) {
            int color = 1, used1, used2, used3, used4;
            if (i - 1 >= 0) used1 = B[i-1][j];
            if (j - 1 >= 0) used2 = B[i][j-1];
            if (i - 1 >= 0 && j - 1 >= 0) used3 = B[i-1][j-1];
            if (i - 1 >= 0 && j + D < N) used4 = B[i-1][j+D];
            while (used1 == color || used2 == color || used3 == color || used4 == color)
                color++;
            for (int a = 0; a < D; a++)
                for (int b = 0; b < D; b++)
                    if (i + a < N && j + b < N)
                        B[i+a][j+b] = color;
        }
    }

    
    auto ans = new int[][](H, W);
    auto color = " RYGB";
    
    foreach (i; 0..H) {
        foreach (j; 0..W) {
            int ni = i + j;
            int nj = i - j + W;
            ans[i][j] = B[ni][nj];
        }
    }

    ans.each!(an => an.map!(a => color[a]).writeln);
}


Measured memory_bytes: 15228
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
 


int main(){
  string s;
  cin >> s;
  int n=s.size();
  ll sumw=0;
  ll sum=0;
  rep(i,n){
    if(s.at(i)=='W'){
	sumw++;
    sum+=(i+1-sumw);
    }
  }
  cout << sum << endl;
    
}

Measured memory_bytes: 640
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n := nextInt(sc)

	vals := make([]int64, n)
	for i := int64(0); i < n; i++ {
		vals[i] = nextInt(sc)
	}

	strVals := make([]string, n)
	var cnt int64
	for i := n - 1; i >= 0; i-- {
		strVals[i] = strconv.FormatInt(vals[cnt], 10)
		cnt++
	}

	fmt.Println(strings.Join(strVals, " "))
}

func nextString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func nextInt(sc *bufio.Scanner) int64 {
	i, err := strconv.ParseInt(nextString(sc), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}



Measured memory_bytes: 1084
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	if(c>=a&&c<=b)
	{
		cout<<"Yes"<<endl;
		return 0;
	}
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
//#define ivorysi
#define pb push_back
#define MAXN 200005
#define eps 1e-12
#define space putchar(' ')
#define enter putchar('\n')
#define mp make_pair
#define fi first
#define se second
#define mo 974711
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 - '0' + c;
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) putchar('-'),x = -x;
    while(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,a[MAXN];
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) read(a[i]);
    a[0] = -1;
    for(int i = 1 ; i <= N ; ++i) {
	if(a[i - 1] < a[i] - 1) {
	    puts("-1");
	    return;
	}
    }
    int64 ans = 0;
    for(int i = N ; i >= 1 ; --i) {
	if(a[i] == a[i + 1] - 1) continue;
	ans += a[i];
    }
    printf("%lld\n",ans);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 1024
#define DEBUG 1

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

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#define MOD 998244353

char X[200000];
int power[200001];
int must[200000];
int num[200001];
int main() {
    int i;
    int N;
    scanf("%d",&N);
    for (i = 0; i < N; i++) scanf(" %c",&X[i]);

    int j;
    LLI ans = 0;
    power[0] = 1;
    for (i = 1; i <= N; i++) power[i] = (2*power[i-1]) % MOD;
    for (i = N; i >= 1; i--) {
        if (((N % i) == 0) && ((N/i) & 1)) {
            LLI x = i,c = 0;
            for (j = i; j <= N; j += i) {
                if (((N % j) == 0) && ((N/j) & 1)) x -= num[j],x %= MOD;
            }
            if (x < 0) x += MOD;
            num[i] = x;
            fill(must,must+i,-1);
            int poss = i;
            for (j = 0; j < N; j++) {
                if (X[j] == '0') {
                    if (must[j % i] == !((j/i) & 1)) break;
                    if (must[j % i] == -1) poss--;
                    must[j % i] = ((j/i) & 1);
                }
                else {
                    if (must[j % i] != !((j/i) & 1)) {
                        int poss2 = poss;
                        if (must[j % i] == -1) poss2--;
                        c += power[poss2],c %= MOD;
                    }
                    if (must[j % i] == ((j/i) & 1)) break;
                    if (must[j % i] == -1) poss--;
                    must[j % i] = !((j/i) & 1);
                }
            }
            if (j == N) c++,c %= MOD;
            ans += c*x,ans %= MOD;
        }
    }
    ans *= 2,ans %= MOD;
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 2048
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <iomanip>
#include <sstream>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
typedef long long ll;

int main() {
	 ll n, k; cin >> n >> k;
	 ll tmp = n/k;
	 ll ans = tmp * tmp*tmp;

	 if (k % 2 == 0) {
		 ll tmp = (n+k/2)/k;
		 ans += tmp * tmp*tmp;
	 }
	 cout << ans << endl;
	 return 0;
}


Measured memory_bytes: 256
n,q=map(int,input().split())
s=input()
a=[]
for i in range(len(s)-1):
  a.append(s[i:i+2])
b=[0]
for i in a:
  b.append(b[-1])
  if i=='AC':
    b[-1]+=1

for i in range(q):
  l,r=map(int,input().split())
  print(b[r-1]-b[l-1])

Measured memory_bytes: 56100
#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int A[200010],c[200010];
struct qwq{int a,b;}seg[800010];
qwq operator+(const qwq&a,const qwq&b){
	if(a.a<b.a)return a;
	else if(a.a>b.a)return b;
	else return{a.a,a.b+b.b};
}
#define mid ((l+r)>>1)
void build(int x,int l,int r){
	seg[x]={0,r-l+1};if(l==r)return;
	build(x<<1,l,mid),build(x<<1|1,mid+1,r);
}
int tag[800010];
void upd(int x,int y){tag[x]+=y,seg[x].a+=y;}
void down(int x){if(tag[x])upd(x<<1,tag[x]),upd(x<<1|1,tag[x]),tag[x]=0;}
void update(int x,int l,int r,const int&L,const int&R,const int&d){
	if(L<=l&&r<=R)return upd(x,d);
	down(x);
	if(L<=mid)update(x<<1,l,mid,L,R,d);
	if(mid<R)update(x<<1|1,mid+1,r,L,R,d);
	seg[x]=seg[x<<1]+seg[x<<1|1];
}
#undef mid
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi(),m=gi(),x,y;
	for(int i=1;i<=n;++i)++c[A[i]=gi()];
	build(1,1,n);
	for(int i=1;i<=n;++i)if(c[i])update(1,1,n,std::max(1,i-c[i]+1),i,1);
	while(m--){
		x=gi(),y=gi();
		int _=A[x];A[x]=y;x=_;
		update(1,1,n,std::max(1,x-c[x]+1),x,-1);
		--c[x];
		if(c[x])update(1,1,n,std::max(1,x-c[x]+1),x,1);
		if(c[y])update(1,1,n,std::max(1,y-c[y]+1),y,-1);
		++c[y];
		update(1,1,n,std::max(1,y-c[y]+1),y,1);
		printf("%d\n",seg[1].a?0:seg[1].b);
	}
	return 0;
}


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

int rec(int p,int q,int a,int n,int last,int prod){
  if(n==0)return 0;

  int res = 0;
  for(int i=min(last,a/prod);i>=1;i--){
    if(p*i-q<=0){
      if(p*i-q==0)res++;
      return res;
    }

    int below = q*i, above = p*i-q;
    //tmp = __gcd(below,above);
    //below/=tmp; above/=tmp;
    
    res += rec(above,below,a,n-1,i,prod*i);
  }
  return res;
}
  
int main(){
  int p,q,a,n;
  while(cin >> p >> q >> a >> n,p){
    cout << rec(p,q,a,n,a,1) << endl;
  }
}

Measured memory_bytes: 1160
#include <stdio.h>

int main() {
	int i, j;
	int x[10000];
	for (i = 0; i < 10000; i++) {
		scanf("%d", &x[i]);
		if (x[i] == 0) break;
	}
	for (j = 0; j < i; j++) {
		printf("Case %d: %d\n", j+1, x[j]);
	}

	return 0;
}


Measured memory_bytes: 2036
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
using namespace std;

#define pa pair<int,int>
#define sc(n) scanf("%d",&n)
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define mem(a,b) memset(a,b,sizeof a)
#define uint unsigned int

const  int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

typedef long long ll;
typedef long double ld;

int a[N],b[N];

int main()
{
	int n,d;
	sc(n);
	fo(i,1,n)
		sc(a[i]),b[i]=a[i];
	sort(a+1,a+n+1);
	int max1=a[n],max2=a[n-1];
	fo(i,1,n)
	{
		if(b[i]!=max1)
			cout<<max1<<endl;
		else
			cout<<max2<<endl;
	}
	return 0;
}

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

using ll = long long;
using pbl = pair<bool, ll>;
int main() {
    ll N;
    cin >> N;
    ll count = N;
    map<ll,pbl> C;
    
    for(ll i=0;i<N;i++){
        ll sub;
        cin >> sub;
        C[sub]=make_pair(true,++C[sub].second);
    }
    ll MAXL = C.rbegin() -> first;
    while(C.size()){
        ll keyy = C.begin()->first;
        pbl temp =C.at(keyy);
        if(temp.first&&temp.second>1)count-=temp.second;
        for(ll j=keyy*2;j<=MAXL;j+=keyy){
            if(C.count(j)&&C.at(j).first){
                count-=C.at(j).second;
                C.at(j).first=false;
            }
        }
        C.erase(keyy);
    }
    
    cout << count << endl;
    
}


Measured memory_bytes: 15920
import math
A, B, H, M = map(int,input().split(" "))


d = abs(6*M - (0.5*M + 30*H))

if d > 180:
    d = 360 - d
ans = math.sqrt(A**2 + B**2 - 2*A*B*math.cos(math.radians(d)))
print(ans)


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

N = int(input())
A = list(map(int, input().split()))
dp = [0]*(N+1)
dp[0] = 1000

for i in range(1, N+1):
    dp[i] = dp[i-1]
    
    for j in range(i):
        dp[i] = max(dp[i], dp[j]//A[j]*A[i-1]+dp[j]%A[j])

print(dp[N])

Measured memory_bytes: 64312
#include <stdio.h>

int main(void)
{
	int n, point[10000][3];
	int i;
	
	while(1){
		scanf("%d", &n);
		if(n == 0)    break;
		
		for(i = 0; i < n; i++)
			scanf("%d %d %d", &point[i][0], &point[i][1], &point[i][2]);
		
		for(i = 0; i < n; i++){
			if(point[i][0] == 100 || point[i][1] == 100 || point[i][2] == 100)
				printf("A\n");
			else if(((point[i][0] + point[i][1]) / 2) >= 90)
				printf("A\n");
			else if(((point[i][0] + point[i][1] + point[i][2]) / 3) >= 80)
				printf("A\n");
			
			else if(((point[i][0] + point[i][1] + point[i][2]) / 3) >= 70)
				printf("B\n");
			else if(((point[i][0] + point[i][1] + point[i][2]) / 3) >= 50
				&& (point[i][0] >= 80 || point[i][0] >= 80))
				printf("B\n");
			
			else
				printf("C\n");
		}
	}
	
	return 0;
}

Measured memory_bytes: 588
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;
typedef vector<VD> VVD;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int w, h, x, y;
    cin >> w >> h >> x >> y;
    printf("%.15f ", 0.5 * w * h);
    cout << (2 * x == w && 2 * y == h) << endl;

    return 0;
}


Measured memory_bytes: 256
// You either die a hero, or you live long enough to see yourself become the villain.

/**
 *   author:  Blind_is_love
 *   created: 12.10.2019, 16:26
**/

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

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;

template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
template <class T, class S> ostream& operator << (ostream &os, const map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE

#define endl "\n"
#define vll vector<int>
#define max_heap priority_queue<int>
#define min_heap priority_queue<int , vector<int>, greater<int> >
#define pb push_back
#define all(container) container.begin(), container.end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define printArr(name,from,to) for(int x = from; x < to; x++) {cout << name[x] << " ";} cout << endl;
#define fi first
#define se second
#define mp make_pair
#define prime1 304933
#define prime2 15486277 
#define mod2 179424691
#define int ll

typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; 

const ll MOD = 1000000007;
const ll MAX = 1e5+10;
const double PI = 3.1415926;
const ll INF = 1e18;
const double EPS = 1e-5;

vll adj[MAX];
int dp[MAX];
bool visited[MAX];

int dfs_visit(int s){
	int f = 0;
	visited[s] = true;
	for(int x : adj[s]){
		if (visited[x]) f = max(f, dp[x]+1);
		else f = max(f, dfs_visit(x) + 1);
	}
	return dp[s] = f;
}

int dfs(int n) {
	int ans = 0;
	for(int i = 0 ; i < n; ++i){
		if (!visited[i]) ans = max(ans, dfs_visit(i));
	}
	return ans;
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	clock_t t1, t2;
	t1 = clock();
	int n,m;
	cin >> n >> m;
	for(int i = 0 ; i < m; ++i){
		int x,y;
		cin >> x >> y;
		x--;y--;
		adj[x].pb(y);
	}
	cout << dfs(n) << endl;

	t2 = clock(); cerr << "time taken: " << (t2-t1)/(long double)CLOCKS_PER_SEC << endl;
	return 0;
}


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

int main() {
	
	int n;
	cin >> n;
	string s;
	cin >> s;
	int c = 0;
	int m = 0;
	for (int i=0; i<s.size(); i++) {
		if (s[i] == 'I') c++;
		else c--;
		m = max(m, c);
	}
	cout << m << endl;
	
}


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

using namespace std;
using ll = long long;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define INF 9223372036854775807
#define all(x) (x).begin(), (x).end()

ll ts = 1000000007;

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

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

  cout << (n == k || k == 1 ? 0 : n - k) << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
//#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
//#include <queue>

using namespace std;
#define n_max 10000
#define INF 10001000

#define rep(i, a, n) for(int i = a; i < n; i++)
#define rep2(i, a, n) for(int i = a; i <= n; i++)
#define rrep(i, a, n) for(int i = a; i > n; i--)
#define rrep2(i, a, n) for(int i = a; i >= n; i--)
#define lrep(i, a, n) for(long int i = a; i < n; i++)
#define in(a) cin >> a
#define out(a) cout << a << endl

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

    cin >> a >> b >> c;

    if(a-b >= c) { cout << 0 << endl; } 
    else         { cout << c - (a-b) << endl; }

    return 0;
}


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

using namespace std;

#define MAX_N 110
#define MAX_R 110
#define MAX_D 110

struct State{
  int r,d;
  State(){}
  State(int r,int d) : r(r),d(d) {}
};

int D,N;
int a[MAX_N],e[MAX_N],r[MAX_N];

int bfs(){
  queue<State> Q; Q.push(State(0,D));
  queue<int> step; step.push(0);
  bool visited[MAX_R][MAX_D] = {{false}};
  visited[0][D] = true;
  while(!Q.empty()){
    State s = Q.front(); Q.pop();
    int stp = step.front(); step.pop();
    if(s.d == 0){ return stp; }
    for(int i = 0 ; i < N ; i++){
      State ns = (State){min(100,s.r+e[i]),max(0,s.d-a[i])};
      if(s.r >= r[i] && !visited[ns.r][ns.d]){
        visited[ns.r][ns.d] = true;
        Q.push(ns);
        step.push(stp+1);
      }
    }
  }
  return -1;
}

int main(){
  while(cin >> D >> N, D){
    for(int i = 0 ; i < N ; i++){
      cin >> a[i] >> e[i] >> r[i];
    }
    int res = bfs();
    if(res == -1){
      cout << "NA" << endl;
    }else{
      cout << res << endl;
    }
  }
  return 0;
}

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

using namespace std;

template <typename T>
ostream& operator<<(ostream& o, const vector<T>& v) {
    o << "[";
    for(size_t i = 0; i < v.size(); i++) {
        o << v[i];
        if(i != v.size() - 1) {
            o << ", ";
        }
    }
    o << "]";
    return o;
}

int main() {
    size_t n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n), b(m);
    for(size_t i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(size_t i = 0; i < m; i++) {
        cin >> b[i];
    }
    int sol = *min_element(a.begin(), a.end()) + *min_element(b.begin(), b.end());
    for(size_t i = 0; i < k; i++) {
        size_t x, y;
        int c;
        cin >> x >> y >> c;
        x--;
        y--;
        sol = min(sol, a[x] + b[y] - c);
    }
    cout << sol << endl;
    return EXIT_SUCCESS;
}


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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<pair<int, int>> a(n);
  int x;
  for (int i = 0; i < n; i++) {
    cin >> x;
    a[i] = {x, i + 1};
  }
  sort(a.begin(), a.end());
  for (int i = 0; i < n; i++) {
    if (i > 0) cout << " ";
    cout << a[i].second;
  }
  cout << endl;

  return 0;
}


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

#define Fast ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO freopen("in.txt", "r", stdin)
#define FC freopen("out.txt", "w", stdout)
#define aise cout<<"aise"<<endl
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define ll long long
#define all(x) x.begin(), x.end()
#define mset(v, a) memset(v, a, sizeof(v))
#define pll pair< ll, ll >
#define pdd pair< double, double >
#define ff first
#define ss second
#define pi acos(-1.0)
#define mxN 2010
#define inf 1e14
#define MOD 1000000007

int main()

{

    ll n;
    cin >> n;
    for(ll i = 0; i*4 <= n; i++)
    {

        for(ll j = 0; (i*4+j*7) <= n; j++)
        {

            if(i*4+j*7==n)
            {

                cout << "Yes";
                return 0;
            }
        }

    }
    cout << "No";
}


Measured memory_bytes: 256
class String
  def to_ia
    self.split(/\s+/).map {|s| s.to_i}
  end
end

def solve(ary)
  puts ary.join(' ')
  n = ary.size
  (1...n).each do |i|
    v = ary[i]
    j = i-1
    while j >= 0 and ary[j] > v
      ary[j+1] = ary[j]
      j -= 1
    end
    ary[j+1] = v
    puts ary.join(' ')
  end
end

STDIN.readline
solve(STDIN.readline.to_ia)

Measured memory_bytes: 8668
#include <iostream>

using namespace std;

int main(){
	int i,d,n;
	cin >> d >> n;
	if(n==100){
		if(d==0){
			cout << 101 << endl;
			return 0;
		}if(d==1){
			cout << 10100 << endl;
			return 0;
		}if(d==2){
		cout << 1010000 << endl;
			return 0;
		}
	}
	
	cout << n ;
	
	for(i=0;i<d;i++){
		cout << "00" ;
	}
	
	cout << endl;
}
		

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

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

const ll MOD  = 1e9 + 7;
const ll LINF = 1LL << 62;
const int INF = 1e9 + 7;

int main(){
    ll n, k;
    cin >> n >> k;

    vector<ll> a(n);
    rep(i, n){
        cin >> a[i];
    }
    sort(ALL(a));



    ll l = 1, r = a[n-1];

    while (r >= l) {
        ll mid = l + (r - l) / 2;

        ll cnt = 0;
        rep(i, n)if(a[i] > mid){
            cnt += a[i] / mid;
        }

        if(cnt <= k)r = mid-1;
        else l = mid + 1;
    }
 
    cout << r+1 << endl;
}


Measured memory_bytes: 4780
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

int main(){
  ll n;
  cin>>n;
  if(n==3){
  	cout << "YES" << endl;
  }
  else if(n==5){
  	cout << "YES" << endl;
  }
  else if(n==7){
  	cout << "YES" << endl;
  }
  else{
  	cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 256