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

using namespace std;

int main()
{
  double x1, y1, x2, y2, ans;

  scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);

  ans = pow(x2 - x1, 2) + pow(y2 - y1, 2);

  printf("%lf", sqrt(ans));
}


Measured memory_bytes: 3204
#include<bits/stdc++.h>
#define lol long long
#define mp make_pair
#define fi first
#define se second
using namespace std;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a[200010];
  double d[200010];
  int n,k;
  double ans=0;
  cin >>n>>k;
  for(int i=0;i<n;i++){
    cin >>a[i];
    d[i]=a[i]*(a[i]+1);
    d[i]/=2;
    d[i]/=a[i];
  }
  double an=0;
  for(int i=0;i<k;i++){
    an+=d[i];
  }
  ans=an;
  for(int i=k;i<n;i++){
    an-=d[i-k];
    an+=d[i];
    if(an>ans) ans=an;
  }
  cout <<fixed<<ans<<'\n';
  return (0);
}


Measured memory_bytes: 2560
package main

import "fmt"

func main() {
	var k, a, b int
	fmt.Scan(&k, &a, &b)

	if a%k == 0 || b%k == 0 || b/k > a/k {
		fmt.Println("OK")
	} else {
		fmt.Println("NG")
	}
}


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

int main() {
	long L, R;
	int ans=2020;
	cin >> L >> R;
	if (R-L>=673)
	{
		ans = 0;
	}
	else
	{
		for (size_t i = L; i <= R; i++)
		{
			for (size_t j = i+1; j <= R; j++)
			{
				ans = min(ans,int( ((i%2019)*(j%2019)))%2019);//それぞれ予め剰余を取らないとあふれる，しかももう一回剰余取らないと2019(すなわち0)を拾えない
			}
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const double eps=1e-8;
inline int sgn(double n) {return fabs(n)<eps?0:(n<0?-1:1);}
inline double sqr(double x) {return x*x;}
inline double Sqrt(double a) {return a<=0?0:sqrt(a);}
int abs(int x) {return x>=0?x:-x;}
struct point
{
	double x,y;
	point(){}
	point(double a,double b):x(a),y(b){}
	friend point operator + (const point &a,const point &b)
	{
		return point(a.x+b.x,a.y+b.y);
	}
	friend point operator - (const point &a,const point &b)
	{
		return point(a.x-b.x,a.y-b.y);
	}
	friend bool operator == (const point &a,const point &b)
	{
		return (sgn(a.x-b.x)==0) && (sgn(a.y-b.y)==0);
	}
	friend point operator * (const point &a,const double &b)
	{
		return point(a.x*b,a.y*b);
	}
	friend point operator * (const double &a,const point &b)
	{
		return point(a*b.x,a*b.y);
	}
	friend point operator / (const point &a,const double &b)
	{
		return point(a.x/b,a.y/b);
	}
	double norm()
	{
		return sqrt(sqr(x)+sqr(y));
	}
}po[70];
point rotate(const point &p,double cost,double sint)
{
	double x=p.x,y=p.y;
return point(x*cost-y*sint,x*sint+y*cost);
}
pair<point,point> crosspoint(point ap,double ar,point bp,double br)
{
	double d=(ap-bp).norm();
	double cost=(ar*ar+d*d-br*br)/(2.0*ar*d);
	double sint=sqrt(1.-cost*cost);
	point v=(bp-ap)/(bp-ap).norm()*ar;
return mp(ap+rotate(v,cost,-sint),ap+rotate(v,cost,sint));
}
double dist(const point &a,const point &b){return (a-b).norm();}
int n,k,topt;
double c[70],ans,r[70];
point now[1000010];
bool ok(double tt)
{
	topt=0;
	for (int i=1;i<=n;i++) r[i]=tt/c[i],now[++topt]=po[i];
	for (int i=1;i<=n;i++)
	 for (int j=i+1;j<=n;j++)
	 if (-eps<=r[i]+r[j]-dist(po[i],po[j]))
	 {
	 	pair<point,point>co=crosspoint(po[i],r[i],po[j],r[j]);
	 	now[++topt]=co.fr; now[++topt]=co.sc;
	 }
	for (int i=1;i<=topt;i++)
	{
		int num=0;
		for (int j=1;j<=n;j++) if (-eps<=r[j]-dist(now[i],po[j])) num++;
		if (num>=k) return 1;
	}
return 0;
}
int main()
{
	//point aa,bb; aa=crosspoint({0,0},1,{1,0},1).fr; bb=crosspoint({0,0},1,{1,0},1).sc;
	//printf("%.8f %.8f\n%.8f %.8f\n",aa.x,aa.y,bb.x,bb.y);
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&po[i].x,&po[i].y,&c[i]);
	double l=0,r=1e8; ans=r;
	for (int _=1;_<=150;_++)
	{
		double mid=(l+r)/2.0;
		if (ok(mid)) {ans=min(ans,mid); r=mid-1;}else l=mid+1;
	}
	printf("%.8f\n",ans);
return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

#include <cmath>
#include <cstdlib>
#include <climits>

//#include <stdio.h>
//#include <stdlib.h>


using namespace std;

#define debug false

int main(int argc, char *argv[]){

  int N;
  cin >> N;
  for(int i = 1; i <= 9; i++){
    if(111 * i >= N){
      cout << 111*i << endl;
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';


using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;

// AtCoder
const i64 CYCLES_PER_SEC = 2800000000;

struct Timer {
	i64 start;
	Timer(){reset();}
	void reset(){start=getCycle();}
	inline double get(){return (double)(getCycle()-start)/CYCLES_PER_SEC;}
	inline i64 getCycle(){
		u32 low,high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((i64)low)|((i64)high<<32);
	}
};

Timer timer;


uint32_t xor128(){
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

//INSERT ABOVE HERE
const int A = 26;
const int MAX_D = 365;
int cs[A+1];
int s[MAX_D+1][A+1];
int ts[MAX_D+1];
int ls[A+1];

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

  int D;
  cin>>D;

  for(int j=1;j<=A;j++) cin>>cs[j];

  for(int i=1;i<=D;i++)
    for(int j=1;j<=A;j++)
      cin>>s[i][j];

  {
    memset(ls,0,sizeof(ls));
    for(int i=1;i<=D;i++){
      vector<int> ss(A+1,0);
      for(int j=1;j<=A;j++)
        ss[j]=s[i][j]+cs[j]*(i-ls[j]);
      ts[i]=max_element(ss.begin()+1,ss.end())-ss.begin();

      ls[ts[i]]=i;
    }
  }

  auto calcScore=[&]()->int{
    int res=0;
    memset(ls,0,sizeof(ls));
    for(int i=1;i<=D;i++){
      res+=s[i][ts[i]];
      ls[ts[i]]=i;
      for(int j=1;j<=A;j++)
        res-=cs[j]*(i-ls[j]);
    }
    return res;
  };

  auto calcDiff=[&](int p,int q)->int{
    int res=0;
    int cp=cs[p],lp=0;
    int cq=cs[q],lq=0;

    for(int i=1;i<=D;i++){
      if(ts[i]==p) res+=s[i][p],lp=i;
      if(ts[i]==q) res+=s[i][q],lq=i;
      res-=cp*(i-lp);
      res-=cq*(i-lq);
    }
    return res;
  };

  int iter_num = 0;
  int tmpScore=calcScore();

  double start_temp = 1000, end_temp = 100;

  const double LIM = 2.0;
  while(timer.get()<LIM){
    iter_num++;
    int d=xor128()%D+1;
    int q=xor128()%A+1;

    int p=ts[d];
    if(p==q) continue;

    int nxtScore=tmpScore;
    nxtScore-=calcDiff(p,q);
    ts[d]=q;
    nxtScore+=calcDiff(p,q);

    // assert(nxtScore==calcScore());

    double temp = start_temp + (end_temp - start_temp) * timer.get() / LIM;
    double prob = exp((nxtScore-tmpScore)/temp);

    const int INF = 1<<30;
    if(prob > (xor128()%INF)/(double)INF){
      tmpScore=nxtScore;
    }else{
      ts[d]=p;
    }
  }

  cerr<<iter_num<<endl;
  cerr<<tmpScore<<":"<<calcScore()<<endl;
  for(int i=1;i<=D;i++) cout<<ts[i]<<newl;
  return 0;
}


Measured memory_bytes: 4344
#include <iostream>
// #include <cassert>
#include <vector>
#include <algorithm>
#include <climits>


// #include <deque>
// #include <stack>
// #include <set>
// #include <map>
// #include <string>
// #include <unordered_set>
// #include <unordered_map>
// #include <queue>
// #include <tuple>

// #include <cmath>
// #include <numeric>

using namespace std;
typedef long long ll;
typedef long l;
typedef pair<long,long> pll;
typedef pair<int,int> pii;
typedef pair<int,long> pil;
typedef pair<long,int> pli;
const char el = '\n';

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

    // int T;
    // cin>>T;
    // cin.ignore();

    // for (int t=0; t<T; ++t) {
        
    // }

    string s;
    cin>>s; cin.ignore();
    bool sawa=false; bool sawb=false;
    for (char c: s) {
        if (c=='A') {
            sawa=true;
        }
        if (c=='B') {
            sawb=true;
        }
    }

    if (sawa&&sawb) {
        cout<<"Yes"<<el;
    } else {
        cout<<"No"<<el;
    }
    
    // long n, m;
    // cin>>n>>m; cin.ignore();

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
    int N;
    cin >> N;
    vector<pair<int, int>> v;
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        v.push_back(make_pair(x, y));
    }
    map<pair<int, int>, int> m;
    int M = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            int p = v[i].first - v[j].first;
            int q = v[i].second - v[j].second;
            M = max(M, ++m[make_pair(p, q)]);
        }
    }
    cout << N-M << endl;
}

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

int dp[10001];
int main(void) {
  int N;
  cin >> N;
  vector<int> s(N);
  for(int i=0;i<N;i++){
    cin >> s[i];
  }


  dp[0] = 1;
  for(int t=0;t<N;t++){
    for(int i=10000;i>=0;i--){
      if(i - s[t] < 0)continue;
      if(dp[i - s[t]]) dp[i] = 1;
    }
  }

  for(int i=10000;i>=0;i--){
    if(dp[i] && i % 10 != 0){
      cout << i << endl;
      return 0;
    }
  }
  cout << 0 << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>  // cin,cout
#include <stdio.h>   // printf,scanf (standard input/output)
#include <cmath>     // abs(x),pow(x,2)
#include <string>
#include <string.h>  // strlen, strcmp
#include <algorithm> // min,max, sort(v.begin(),v.end())
#include <vector>
#include <time.h>
using namespace std;

struct Card{
    string suit;
    int value;
};

int Func(){
    int x = 0;
    return x;
}

int main(){
    int N, A[1000];
    float f;
    string S;
    
    cin >> S;
    //for (int i=0;i<N;i++) cin >> A[i];
    
    Card C1[100], C2[100];
    //for (int i=0;i<N;i++) cin >> C1[i].suit >> C1[i].value;
    //for (int i=0;i<N;i++) C2[i] = C1[i];
    
    
    int a = stoi(S.substr(5,2));
    int b = stoi(S.substr(8,2));
    //cout << a << endl;
    
    if (a<=4 and b<=30) cout << "Heisei" << endl;
    else cout << "TBD" << endl;
    
    
    return 0;
}


Measured memory_bytes: 256
h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
dx=[1,1,1,0,0,-1,-1,-1]
dy=[1,0,-1,1,-1,1,0,-1]
for i in range(h):
  for j in range(w):
    if l[i][j]=='.':
      count=0
      for k in range(8):
        nx=i+dx[k]
        ny=j+dy[k]
        if nx<0 or ny<0 or nx>=h or ny>=w:
          continue
        else:
          if l[nx][ny]=='#':
            count+=1
      l[i][j]=str(count) 
for i in l:
  print(''.join(i))

Measured memory_bytes: 3188
import sys
def input():
    return sys.stdin.readline().rstrip()
def main():
    moji=input()
    cycle=int(input())
    flont_or_back=0
    flont=""
    back=""
    for i in range(cycle):
        line=input()
        if line[0]=="1":
            flont_or_back+=1
        else:
            fi=line[2]
            ci=line[4]
            if flont_or_back%2==0:
                if fi=="1":
                    flont=ci+flont
                else:
                    back+=ci
            else:
                if fi=="1":
                    back+=ci
                else:
                    flont=ci+flont
    moji=flont+moji+back
    if flont_or_back%2==0:
        print(moji)
    else:
        print(moji[::-1])
    

if __name__ == '__main__':
    main() 
  


Measured memory_bytes: 4692
#include <vector>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <map>

typedef long long ll;
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ALL(a) begin(a), end(a)
#define mii map<int, int>
#define msi map<string, int>
#define vi vector<int>
#define vl vector<ll>
#define MOD 1000000007
#define INF 1e9
#define showVector(v) rep(i,0,v.size()){p(v[i]);p(" ")} pl("")
#define p(s) std::cout << s ;
#define pl(s)  std::cout << s << endl;
using namespace std;

// 素数判定 O(√n)
bool is_prime(int n){
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}

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;
}
int main() {
    int N;
    cin >> N;
    double ans = 0;
    vector<double> a(N);
    rep(i, 0, N) {
        cin >> a[i];
        ans += a[i];
    }
    ans = ans/N;

    double b = INF;
    rep(i, 0, N) {
        b = min(abs(a[i]-ans), b);
    }
    rep(i, 0, N) {
        if (abs(a[i]-ans) == b) {
            cout << i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <cstdio>
#include <string.h>
#include <vector>
#include <functional>
#include <stack>
#include <queue>
#include <string>
#include <list>
using namespace std;
typedef long long ll;
/* prototype */
int EDSum(ll);//各桁の和
vector<int> SOE(int,int);//素数 (Min,Max)
int MinCM(int,int);//最小公倍数(num1,num2)
int MaxCD(int,int);//最大公約数(num1,num2)
vector<int> igets(int);//cin * N
ll nPr(ll,ll); //(n,r)
ll nE(ll); //(n)
ll nCr(ll,ll); //(n,r)

void solve(){
    //START
  	vector <int> A = igets(3);
  	sort(A.begin(),A.end());
    if(A[0]+A[1]==A[2])cout << "Yes"<< endl; else cout << "No"<< endl;
}

int main(void){cin.tie(0);ios::sync_with_stdio(false);solve();}
/*FUNC*/
//各桁の和
int EDSum(ll number){
    int ans=0;
    while(1){
        ans += number % 10;
        number /= 10;
        if(number == 0) break;
    }
    return ans;
}

//エラトステネスのふるい(素数発見アルゴリズム)
vector<int> SOE(int min, int max)
{
    //0,1は含まれない
    if (min < 2) min = 2;
    //探索リスト作成
    vector<int> int_array;
    for (int i = min; i <= max; i++) int_array.push_back(i);
    //素数リスト
    vector<int> sosu;
    //√max
    double stop = sqrt(max);
    //計算
    while (true)
    {
        //素数リストに追加
        sosu.push_back(int_array.front());
        int_array.erase(int_array.begin());
        //停止
        if (stop < (double)(sosu.back())) break;
        //ふるい
        for (int i = 0; i < (int)int_array.size(); i++)
        {
            if (int_array[i] % sosu.back() == 0)
                int_array.erase(int_array.begin() + i);
        }
    }
    sosu.insert(sosu.end(), int_array.begin(), int_array.end());
    return sosu;
}

//最小公倍数
int MinCM(int a, int b)
{
    int c = a * b;
//入れ替え
    if (a < b)
        swap(a, b);
    int r = a % b;
    while (r != 0)
    {
        a = b;
        b = r;
        r = a % b;
    }
    return c / b;
}

//最大公約数
int MaxCD(int a, int b)
{
//入れ替え
    if (a < b)
        swap(a, b);
    int r = a % b;
    while (r != 0)
    {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}
//iget cin int 2 vector
vector<int> igets(int N){
    vector<int> A;
    int temp;
    for (int i = 0; i < N; ++i) {
        cin >> temp;
        A.push_back(temp);
    }
    return A;
}

ll nPr(ll n,ll r) {
    ll ans=1;
    r=n-r;
    while(n!=r) {
        ans*=n;
        --n;
    }
    return ans;
}

ll nE(ll n) {
    return nPr(n,n);
}

ll nCr(ll n,ll r) {
    if(r==0)return -1;
    else{
        if(0!=n-r&&n-r<r)r=n-r;
        return nPr(n,r)/nE(r);
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

ll gcd(ll a, ll b) {
    while (b) {
        ll c = a % b;
        a = b;
        b = c;
    }
    return a;
}

ll po(ll a, ll b) {
    ll c = 1;
    while (b) {
        if (b % 2) c = c * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return c;
}

ll f[2000006], g[2000006];

void comb() {
    f[0] = 1;
    for (int i = 1; i <= 2000000; i++) f[i] = f[i - 1] * i % mod;
    g[2000000] = 407182070;
    for (int i = 1999999; i >= 0; i--) g[i] = g[i + 1] * (i + 1) % mod;
}

int p[200005];

int root(int x) {return p[x] < 0 ? x : p[x] = root(p[x]);}

void mer(int x, int y) {
    if ((x = root(x)) == (y = root(y))) return;
    if (p[x] > p[y]) swap(x, y);
    p[x] += p[y];
    p[y] = x;
}

int n, t[100005];

void inc(int x) {
    for (; x <= n; x += x & -x) t[x]++;
}

int que(int x) {
    int z = 0;
    for (; x; x -= x & -x) z += t[x];
    return z;
}

int main() {
    ios::sync_with_stdio(false);
    int a[100005] = {}, b[100005] = {}, c[100005] = {}, d[100005] = {}, e[100005] = {}, f[100005] = {};
    ll z = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], f[a[i]] = i;
    a[0] = a[n + 1] = n + 1;
    for (int i = n; i; i--) {
        int l = 0, r = f[i];
        while (l + 1 < r) {
            int m = (l + r) / 2;
            if (que(f[i]) - que(m - 1) < 1) r = m;
            else l = m;
        }
        b[f[i]] = l;
        l = 0, r = f[i];
        while (l + 1 < r) {
            int m = (l + r) / 2;
            if (que(f[i]) - que(m - 1) < 2) r = m;
            else l = m;
        }
        c[f[i]] = l;
        l = f[i], r = n + 1;
        while (l + 1 < r) {
            int m = (l + r) / 2;
            if (que(m) - que(f[i]) < 1) l = m;
            else r = m;
        }
        d[f[i]] = r;
        l = f[i], r = n + 1;
        while (l + 1 < r) {
            int m = (l + r) / 2;
            if (que(m) - que(f[i]) < 2) l = m;
            else r = m;
        }
        e[f[i]] = r;
        //for (int j = 1; j <= n; j++) cout << que(j) << ' '; cout << '\n';
        inc(f[i]);
    }
    for (int i = 1; i <= n; i++) {
        //cout << b[i] << ' ' << c[i] << ' ' << d[i] << ' ' << e[i] << '\n';
        z += 1ll * a[i] * (b[i] - c[i]) * (d[i] - i) + 1ll * a[i] * (i - b[i]) * (e[i] - d[i]);
    }
    cout << z;
}


Measured memory_bytes: 6352
#include <iostream>

using namespace std;

int main() {
    int64_t a, b;

    cin >> a >> b;

    if (a < b) {
        int64_t temp = a;
        a = b;
        b = temp;
    }

    while (b != 0) {
        int64_t temp = a % b;
        a = b;
        b = temp;
    }

    cout << a << endl;

    return 0;
}

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

public class Main {

	public static String Y = "Yes";
	public static String N = "No";
	public static long MOD = (long) (Math.pow(10, 9) + 7);
	public static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int n = ni();

		int[] p = new int[n];

		String pi = "";
		String[] piSort = new String[n];

		for (int i = 0; i < n; i++) {
			p[i] = ni();
			pi += "" + p[i] + " ";
		}

		piSort = pi.split(" ", 0);

		Arrays.sort(p);

		int count = 0;

		for (int i = 0; i < n; i++) {
			if (!(Integer.parseInt(piSort[i]) == p[i])) {
				count++;
			}

		}

		if (count == 2 || count == 0) {
			out("YES");
		} else {
			out("NO");
		}

	}

	/*
	 * 以下メソッド集
	 */

	static int ketasuu(int n) {
		String str = "" + n;
		return str.length();
	}

	static int abcount(String str) {
		int count = 0;
		int len = str.length();
		for (int i = 0; i < len - 1; i++) {
			if ("AB".equals(str.substring(i, i + 2))) {
				count++;
			}
		}
		return count;
	}

	static int ni() {
		return sc.nextInt();
	}

	static long nl() {
		return sc.nextLong();
	}

	static double nd() {
		return sc.nextDouble();
	}

	static String n() {
		return sc.next();
	}

	static char[] nc() {
		return sc.next().toCharArray();
	}

	static int kaijo(int n) {
		if (n == 0 || n == 1) {
			return 1;
		} else {
			return n * kaijo(n - 1);
		}
	}

	static int fib(int n) {
		return (n == 1 || n == 0) ? n : fib(n - 2) + fib(n - 1);
	}

	static long lcm(long m, long n) {

		return m * n / gcd(m, n);
	}

	static int lcm(int m, int n) {

		return m * n / gcd(m, n);
	}

	static long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static void out(String info) {
		System.out.println(info);
	}

	static void out(int info) {
		System.out.println(info);
	}

	static void out(double info) {
		System.out.println(info);
	}

	static void out(long info) {
		System.out.println(info);
	}

	static void out(char info) {
		System.out.println(info);
	}

	static void out(Object obj) {
		System.out.println(obj.toString());
	}

	static void outn(String info) {
		System.out.print(info);
	}

	static void outn(int info) {
		System.out.print(info);
	}

	static void outn(double info) {
		System.out.print(info);
	}

	static void outn(long info) {
		System.out.print(info);
	}

	static void outn(char info) {
		System.out.print(info);
	}

	static double max(double d, double e) {
		return Math.max(d, e);
	}

	static long max(long a, long b) {
		return Math.max(a, b);
	}

	static double min(double d, double e) {
		return Math.min(d, e);
	}

	static long min(long a, long b) {
		return Math.min(a, b);
	}
}

class XY {
	int h;
	int c;

	XY(int h, int c) {
		this.h = h;
		this.c = c;
	}
}


Measured memory_bytes: 23892
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define REPD(i,a,b) for (int i=(a);i<(b);i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef set<int> si;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pi;
typedef queue<pi> qpi;
typedef pair<ll, ll> pll;
typedef queue<pll> qpll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const int mod = 1000000007;
const int INF = 1001001001;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 円周率　M_PI
// 文字判定　isupper islower
// 順列　do {} while(next_permutation(ALL(X)));
// 最大値　LLONG_MAX
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;
unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
int main() {
  char s[3];
  cin >> s;
  if(s[1]=='B') {
    cout << "ARC" << endl;
  } else {
    cout << "ABC" << endl;
  }
  return 0;
}


Measured memory_bytes: 3592
from sys import stdin


def main():
    lines = stdin.readlines()
    N = int(lines[0])
    Tn = [0] * N
    An = [0] * N
    for i in range(N):
        Tn[i], An[i] = map(int, lines[i + 1].split())
    T = 1
    A = 1
    for Ti, Ai in zip(Tn, An):
        n = max(-(-T // Ti), -(-A // Ai))
        T = n * Ti
        A = n * Ai
    print(T + A)
    return


main()


Measured memory_bytes: 3188
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w, a, b = MAP()

s = [[0]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if ( i < b and j >= a ) or ( i >= b and j < a ):
            s[i][j] = 1

for i in range(h):
    print(*s[i][:], sep="")

Measured memory_bytes: 18664
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
#include <stdlib.h>
using namespace std;



int main()
{
  int ans[26] = {};
  int n,i,j;  cin >> n;
  string s;
  cin >> s;
  for(i=0;i<s.length();i++){
    int tmp = char(s[i]) - 'a';
    ans[tmp]++;
  }

  for(i=1;i<n;i++){
    int tmp[26] = {};
    cin >> s;
    for(j=0;j<s.length();j++){
      int t = char(s[j]) - 'a';
      tmp[t]++;
    }
    for(j=0;j<26;j++)
      ans[j] = min(ans[j],tmp[j]);
  }
  int res = 0;
  for(i=0;i<26;i++)
    for(j=0;j<ans[i];j++)
      cout << char('a' + i) ;

  cout << endl;

  return 0;
}

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

int main()
{
    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;
    
    if( (x - r) >= 0 && (x + r) <= W && (y - r) >= 0 && (y + r) <= H)
    {
        cout << "Yes" << endl;
        return 0;
    }
    
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3088
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <ctime>

using namespace std;

int q, h, s, d, n;

void Work()
{
	scanf("%d%d%d%d%d", &q, &h, &s, &d, &n);
	h = min(h, 2 * q);
	s = min(s, 2 * h);
	d = min(d, 2 * s);
	long long ans = (long long) (n / 2) * (long long) d + (long long) (n % 2) * (long long) s;
	printf("%lld\n", ans);
}

int main()
{
	Work();
	return 0;
}


Measured memory_bytes: 128
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=998244353;
//const ll mod=1000000007;
const vector<int> dy={-1,0,1,0},dx={0,-1,0,1};
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T>void debag(const vector<T> &a){cerr<<"debag :";for(auto v:a)cerr<<v<<" ";cerr<<"\n";}
template<class T>void print(const vector<T> &a){for(auto v:a)cout<<v<<" ";cout<<"\n";}
pair<int,int> dp[(1<<18)+5]={};
int main(){
    int n;
    cin>>n;
    for(int i=0;i<(1<<n);i++){
        cin>>dp[i].fi;
    }
    for(int j=0;j<n;j++){
        for(int i=0;i<(1<<n);i++){
            if(i&(1<<j)){
                V<int> d={dp[i].fi,dp[i].se,dp[i&~(1<<j)].fi,dp[i&~(1<<j)].se};
                sort(all(d),greater<int>());
                dp[i].fi=d[0];
                dp[i].se=d[1];
            }
        }
    }
    int ans=-1;
    for(int i=1;i<(1<<n);i++){
        chmax(ans,dp[i].fi+dp[i].se);
        cout<<ans<<"\n";
    }
}

Measured memory_bytes: 5652
#include <iostream>
#include <cmath>

using namespace std;

int main() {
	int n;
	bool hantei = false;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		int data[4];
		cin >> data[0] >> data[1] >> data[2] >> data[3];
		int counter = 10000000;
		int data2[4] = {0};
		for (int i = 0; i <= data[0]; i++) {
			for (int j = 0; j <= data[1]; j++) {
				for (int k = 0; k <= data[2]; k++) {
					for (int l = 0; l <= data[3]; l++) {
						int mm = i*10+j*50+k*100+l*500;
						int a = i+j+k+l;
						if (mm >= n) {
							int otsu = mm-n;
							int counter2 = 0;
							if (otsu >= 500) {
								counter2 += otsu/500;
								if (l > 0 && otsu/500 > 0) {
									continue;
								}
								otsu %= 500;
							}
							if (otsu >= 100) {
								counter2 += otsu/100;
								if (k > 0 && otsu/100 > 0) {
									continue;
								}
								otsu %= 100;
							}
							if (otsu >= 50) {
								counter2 += otsu/50;
								if (j > 0 && otsu/50 > 0) {
									continue;
								}
								otsu %= 50;
							}
							if (otsu >= 10) {
								counter2 += otsu/10;
								if (i > 0 && otsu/10 > 0) {
									continue;
								}
							}
							counter2 -= a;
							if (counter == 10000000) {
								counter = counter2;
								data2[0] = i;
								data2[1] = j;
								data2[2] = k;
								data2[3] = l;
							} else {
								if (counter2 <= counter) {
									counter = counter2;
									data2[0] = i;
									data2[1] = j;
									data2[2] = k;
									data2[3] = l;
								}
							}
						}
					}
				}
			}
		}
		int data3[4] = {10, 50, 100, 500};
		if (hantei) {
			cout << endl;
		}
		for (int i = 0; i < 4; i++) {
			if (data2[i] > 0) {
				cout << data3[i] << ' ' << data2[i] << endl;
			}
		}
		hantei = true;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>

using namespace std;

int main() {
    int before_rate, after_rate, before_sum;
    while (cin >> before_rate >> after_rate >> before_sum) {
        if (before_rate == 0 && after_rate == 0 && before_sum == 0) break;

        int max_sum = 0;
        for (int i = 1; i <= before_sum; i++) {
            for (int j = 1; j <= before_sum; j++) {
                if ((i * (100 +  before_rate) / 100) + (j * (100 + before_rate) / 100) == before_sum) {
                    int after_sum = (i * (100 +  after_rate) / 100) + (j * (100 + after_rate) / 100);
                    max_sum = max(after_sum, max_sum);
                }
            }
        }

        cout << max_sum << endl;
    }

    return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
const ll mod = ll(1e9) + 7;
const int INF = int(1e9);
int main()
{
    int N;
    cin >> N;
    int ans = 0;
    vector<int> V(N), C(N);
    rep(i, N) cin >> V[i];
    rep(i, N) cin >> C[i];
    rep(i, N)
    {
        ans += (V[i] - C[i] > 0 ? V[i] - C[i] : 0);
    }
    cout << ans << endl;
    return 0;
}


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

//#define DEBUG


int main(void)
{
  ll N,A,B;
  cin >> N >> A >> B;
  // 商とあまり
  ll sho, amari;
  sho = N/(A+B);
  amari = N%(A+B);
  // あまりの中の青の個数
  ll ba;
  if(amari>A)
  {
    ba = A;
  }else{
    ba = amari;
  }
  
  // 青の個数
  ll bn;
  bn = sho * A + ba;
  cout << bn;
  return 0;
} 

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int dp[1010][1010];

int main(void){
	int i,j,k;

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

	int q;
	cin >> q;
	for(i=0;i<q;i++){
		string x,y;
		cin >> x >> y;
		int n=x.size(),m=y.size();

		for(j=0;j<=n;j++) for(k=0;k<=m;k++) dp[j][k]=0;

		for(j=1;j<=n;j++){
			for(k=1;k<=m;k++){
				if(x[j-1]==y[k-1]) dp[j][k]=dp[j-1][k-1]+1;
				else dp[j][k]=max(dp[j][k-1],dp[j-1][k]);
			}
		}

		cout << dp[n][m] << endl;

	}

	return 0;
}

Measured memory_bytes: 5164
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef pair<int,int> P;
typedef long long ll; 

ll mod = 1e9 + 7;

int main(){
	int n;
	int v[50];
	
	cin >> n;
	for(int i=0;i<n;i++) cin >> v[i];

	sort(v,v+n);

	double ans = v[0];
	for(int i=1;i<n;i++){
		ans += v[i];
		ans /= 2.0;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 384
s = input()

t = ""

a = "dream"
b = "dreamer"
c = "erase"
d = "eraser"

s = s.replace(d,"")
s = s.replace(c,"")
s = s.replace(b,"")
s = s.replace(a,"")

if s == "":
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vll = vector<vl>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const ll INF = 2e15;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

ll evaluate(int contest,int date,vector<ll>&last,vector<ll>&c,vll&s){
  ll point_today = 0;
  point_today += s[date][contest];
  ll minus = 0;
  for (ll j=1; j <= 26;j++){
    minus += c[contest] * (date - last[contest]);
  }
  return point_today;
}

int main(){
  ll d;
  cin >> d;
  vl c(27);
  for(ll i=1;i<=26;i++){
    cin >> c[i];
  }
  vll s(d + 1, vl(27));
  for (ll i = 1; i <= d;i++){
    for (ll j = 1; j <= 26;j++){
      cin >> s[i][j];
    }
  }
  vl t;
  vl last(27, 0);
  ll satisfy = 0;
  for (ll date = 1; date <= d;date++){
    priority_queue<pair<ll, int>> q;
    for (ll contest = 1; contest <= 26;contest++){
      q.push(mp(evaluate(contest, date, last,c,s), contest));
    }
    t.pb(q.top().S);
    satisfy += q.top().F;
    last[q.top().S] = date;
  }
  rep(i,d){
    print(t[i]);
  }
}

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

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


		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] c = br.readLine().split(" ");

		int[] a = new int[n];

		for(int i=0; i<n; i++) {
			a[i] = Integer.parseInt(c[i]);
		}

		int counter=0;
		while(true) {
			Boolean b = true;
			for (int i = 0; i < a.length; i++) {
				if(a[i] % 2 != 0) {
					b = false;
				}
			}

			if (!b) {
				break;
			}

			for (int j = 0; j < a.length; j++) {
				a[j] = a[j] / 2;
			}
			counter++;
		}

		System.out.println(counter);


	}



}

Measured memory_bytes: 21076
#include<iostream>
#include<string>
using namespace std;
int main(){
  string num;
  cin >> num;
  while(num[0]!='0'){
    int i,sum=0;
    for(i=0;i<num.size();i++){
      sum+=num[i]-'0';
    }
    cout << sum << endl;
    cin >> num;
  }
  return 0;
}




Measured memory_bytes: 3200
//In the name of Allah
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1000 * 100 + 100; 
typedef long long ll; 


ll a[maxN]; 
ll z[maxN]; 
ll pref[maxN];
ll ans[maxN]; 


int main() {
	ios::sync_with_stdio(false); cin.tie(0); 
	int n,q; cin >> n >> q; 
	a[0] = n; 
	int en = 1; 
	for( int i = 0 ; i < q ; i++ ) { 
		ll x; cin >> x; 
		while( en > 0 && a[en-1] >= x ) 
			en--; 
		a[en++] = x; 
	}

	q = en; 
	z[q-1] = 1; 
	for( int i = q - 1 ; i > 0 ; i-- ) { 
		ll d = a[i] / a[i-1]; 
		z[i-1] += d * z[i]; 
		ll rem = a[i] % a[i-1]; 
		while( rem > a[0] ) { 
			int ind = upper_bound( a , a + i , rem ) - a - 1; 
			z[ind] += rem / a[ind] * z[i]; 
			rem = rem % a[ind];
			//cerr << "H "  << rem << endl;
		}
		//cerr << " ! "  << rem << endl;
		pref[rem]+= z[i]; 
	}
	for( int i = n - 1 ; i >= 0 ; i-- ) { 
		pref[i] += pref[i+1]; 
		ans[i] = pref[i+1] + z[0]; 
		if( i >= a[0] ) ans[i] = 0;
	}
	for( int i = 0 ; i < n ; i++ ) 
		cout << ans[i] << '\n'; 
}


Measured memory_bytes: 4864
#include <cstdio>
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;

int main()
{
	vector<int> r(3);
	int tcounter = 0;
	int ecounter = 0;
	int dcounter = 0;
	for (int i = 0; i < 100000000; i++) {
		cin >> r[0] >> r[1] >> r[2];
		sort(r.begin(), r.end());
		if (r[0] + r[1] > r[2]) {
			if (r[0] * r[0] + r[1] * r[1] > r[2] * r[2]) ecounter++;
			else if (r[0] * r[0] + r[1] * r[1] < r[2] * r[2]) dcounter++;
			else tcounter++;
		}
		else {
			cout << i << " " << tcounter << " " << ecounter << " " << dcounter << endl;
			break;
		}
	}
}


Measured memory_bytes: 3132
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;

int main()
{
	int N;
	long long W;
	cin >> N >> W;
	vector<long long> v[4];
	for (auto i = 0; i < 4; ++i)
	{
		v[i].push_back(0);
	}

	long long w1, v1;
	cin >> w1 >> v1;
	v[0].push_back(v1);
	for(auto i = 1; i < N; ++i)
	{
		long long a, b;
		cin >> a >> b;
		v[a - w1].push_back(b);
	}

	for (auto i = 0; i < 4; ++i)
	{
		sort(v[i].begin() + 1, v[i].end(), greater<long long>());
		for (auto j = 1; j < v[i].size(); ++j)
		{
			v[i][j] += v[i][j - 1];
		}
	}

	auto result = 0ll;
	for (auto i = 0; i < v[0].size(); ++i)
	{
		for (auto j = 0; j < v[1].size(); ++j)
		{
			for (auto k = 0; k < v[2].size(); ++k)
			{
				auto temp = i * w1 + j * (w1 + 1) + k * (w1 + 2);
				if (temp > W)
				{
					continue;
				}

				auto l = min((long long)v[3].size() - 1, (W - temp) / (w1 + 3));

				auto sum = v[0][i] + v[1][j] + v[2][k] + v[3][l];

				result = max(result, sum);
			}
		}
	}

	cout << result << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std ;
int main()
{
 char x ; 
  cin >> x ;
  if(x == 'A')
    cout << 'T' ;
  else if(x == 'T')
  	cout << 'A' ;
  else if(x == 'G')
  	cout << 'C' ;
  else if(x == 'C')
    cout << 'G' ;
  
  return 0 ;
}

Measured memory_bytes: 256
S = input()
flag = True
C_cnt = 0
for i in range(len(S)):
    if i==0:
        if S[i]!="A":
            flag = False
            break
    elif i>=2 and i<len(S)-1:
        if S[i]=="C":
            C_cnt += 1
        elif ord(S[i]) < 97 or ord(S[i]) > 122:
            flag = False
            break
    else:
        if ord(S[i]) < 97 or ord(S[i]) > 122:
            flag = False
            break
if flag==True and C_cnt==1:
    print("AC")
else:
    print("WA")

Measured memory_bytes: 3064
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static void solve() {
		int n = in.nextInt();
		int[] a = new int[n];
		for (int i=0; i<n; i++) {
			a[i] = in.nextInt() - 1;
		}
		int cnt = 0;
		for (int i=0; i<n; i++) {
			if (a[a[i]] == i) {
				cnt++;
			}
		}
		out.println(cnt/2);
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		solve();
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

Measured memory_bytes: 32344
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

N,TT = map(int,input().split())
C,T = [],[]
for i in range(N):
    c,t = map(int,input().split())
    C.append(c)
    T.append(t)

ans = max(C)+1

for i in range(N):
    t,c = T[i],C[i]
    if t <= TT:
        if ans > c:
            ans = c
if ans == max(C) + 1:
    print('TLE')
else:
    print(ans)


Measured memory_bytes: 5676
n, m = list(map(int, input().split()))
MOD = 1000000007

dp = [0 for i in range(n+2)]
dp[0] = 1
a = set()
for i in range(m):
  t = int(input())
  a.add(t)

for i in range(n):
  if i+2 not in a:
    dp[i+2] = (dp[i+2]+dp[i])%MOD
  if i+1 not in a:
    dp[i+1] = (dp[i+1]+dp[i])%MOD

print(dp[n])

Measured memory_bytes: 12832
#include <bits/stdc++.h>
using namespace std;
int main(){for(int m,n,t;cin>>n,n;){int a[n];for(m=n;t=m--;)cin>>a[m];sort(a,a+n);for(m=n-1;--m;)t+=a[m];cout<<t/(n-2)<<endl;}return 0;}

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

typedef long long ll;

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	vector<ll> mat(n);
	ll rsum = 0;
	for(int i = 0;i < n; ++i){
		cin >> mat[i];
		rsum ^= mat[i];
	}
	for(int i = 0;i < n; ++i){
		mat[i] &= (~rsum);
	}
	ll l = 0; 
	ll ans = 0;
	for(int i = 63;i >= 0; --i){
		for(int j = l; j < n; ++j){
			if((mat[j] >> i) & 1){
				swap(mat[l], mat[j]);
			}
		}
		if(((mat[l] >> i)&1) == 0)continue;
		for(int j = 0;j < n; ++j){
			if(j == l)continue;
			if((mat[j] >> i) & 1){
				mat[j] ^= mat[l];	
			}
		}
		++l;
		if(l >= n)break;
	}
	for(int i = 0;i < n; ++i){
		ans^=mat[i];
	}

	cout << 2 * ans + rsum << '\n';
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= (int)end; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int D;
    cin >> D;
    vector<int> C(26);
    for (auto& c : C) {
        cin >> c;
    }
    vector<vector<int>> S(D, vector<int>(26));
    rep(i, 0, D) rep(j, 0, 26) {
        cin >> S[i][j];
    }
    vector<int> T(D);
    for (auto& t : T) {
        cin >> t;
    }
    vector<int> last_day(26, 0);
    int score = 0;
    rep(i, 0, D) {
        score += S[i][T[i] - 1];
        last_day[T[i] - 1] = i + 1;
        rep(j, 0, 26) {
            score -= C[j] * (i + 1 - last_day[j]);
        }
        cout << score << endl;
    }
    return 0;
}

Measured memory_bytes: 3696
from collections import defaultdict, deque, Counter

N = int(input())

counter = Counter()
nodes = defaultdict(list)
edges = []

for i in range(N - 1):
    u, v = map(int, input().split(' '))
    nodes[u].append((v, i))
    nodes[v].append((u, i))
    edges.append((u, v))

K = 0
for node in nodes.values():
    K = max(K, len(node))

checked = set()
queue = deque([(1, 0)])
edge_colors = [0] * N

while queue:
    u, uc = queue.popleft()
    checked.add(u)
    color = 1
    for v, e in nodes[u]:
        if v in checked:
            continue
        if color == uc:
            color += 1
        edge_colors[e] = color
        queue.append((v, color))
        color += 1

print(K)
for i in range(N - 1):
    print(edge_colors[i])


Measured memory_bytes: 122552
//g++ -Wshadow -Wall -o A.cpp a -g -fsanitize=address -fsanitize=undefined 
#include <bits/stdc++.h>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define TC int tc; cin >> tc; while(tc--)

using namespace std;

const int INF = 1e9 + 7;
const int MxN = 2e5 + 10;

int n, m;
vector<int> adj[MxN], ord, seen, dp;

void dfs(int v){
	seen[v] = 1;
	for(int u : adj[v]){
		if(!seen[u])dfs(u);
	}
	ord.pb(v);
	return;
}

int main(void)
{
	FAST
	cin >> n >> m;

	seen.assign(n, 0);
	dp.assign(n, 0);

	while(m--){
		int u, v;
		cin >> u >> v;
		u--; v--;
		adj[u].pb(v);
	}


	for(int i = 0; i < n; i++)
		if(!seen[i]) dfs(i);

	reverse(ord.begin(), ord.end());
	
	for(int v : ord){
		for(int u : adj[v]){
			dp[u] = max(dp[u], dp[v] + 1);
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++){
		ans = max(ans, dp[i]);
	}
	cout << ans << '\n';

	return 0;
}


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

int main() {
	//input
	int K, A, B;
	cin >> K >> A >> B;

	//calculation
	int temp = (A + K - 1) / K;

	if (temp * K <= B) {
		cout << "OK" << endl;
	} else {
		cout << "NG" << endl;
	}


	return 0;
}


Measured memory_bytes: 3636
N = int(input())
now_x = 0
now_y = 0
now_time = 0
ans = 1
for i in range(N):
    t, x, y = map(int, input().split())
    distance = abs(now_x - x) + abs(now_y - y)
    time = t - now_time
    sa = time-distance
    if sa >= 0 and sa % 2 == 0:
        now_x, now_y, now_time = x, y, t
        continue
    else:
        ans = 0
        continue

if ans == 1:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define str string
#define fi first
#define se second
#define pb push_back
#define SET(a, b) memset(a, b, sizeof(a))
#define eps 1e-6
#define pi atan(1) * 4
#define mod 1000000007
#define inf 1000000000
#define llinf 1000000000000000000
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define FORl(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORDl(i, a, b) for (ll i = (a); i >= (b); i--)
using namespace std;
int main () {
  string S, T;
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> S >> T;
  int s = S.length();
  int t = T.length();
  if (t != s + 1) {
    printf("No\n");
  } else {
    FOR(i, 0, s - 1) {
      if (S[i] != T[i]) {
        printf("No\n"); return 0;
      }
    }
    printf("Yes\n");
  }
  return 0;
}

Measured memory_bytes: 3616
#include <iostream> // C++の入出力
#include <stdio.h> // C の入出力
#include <algorithm> // sort などのアルゴリズム 
#include <string.h> // C の文字列用
#include <ctype.h> // C の文字種用
#include <string> // C++の文字列
using namespace std; // std 名前空間を使用する

int main(void){
    int n,a,b,cal;
    scanf("%d",&n);
    int d[n];
    scanf("%d %d",&a,&b);
    scanf("%d",&cal);
    for(int i=0;i<n;i++){
        scanf("%d",&d[i]);
    }
    sort(d,d+n);
    reverse(d,d+n);
    for(int i=0;i<n;i++){
        if((cal+d[i])/(a+b)>=cal/a){
            cal += d[i];
            a += b;
        }
    }
    printf("%d\n",cal/a);
}

Measured memory_bytes: 1208
a = input() + "0"
b = input() + "0"
c = input() + "0"
a_coun = 0
b_coun = 0
c_coun = 0
next = "a"
f = True
while f:
    if next == "a":
        if a[a_coun] == "0":
            print("A")
            break
        next = a[a_coun]
        a_coun += 1
    elif next == "b":
        if b[b_coun] == "0":
            print("B")
            break
        next = b[b_coun]
        b_coun += 1
    elif next == "c":
        if c[c_coun] == "0":
            print("C")
            break
        next = c[c_coun]
        c_coun += 1

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <cstdlib>
#define ll long long
#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define MX 100010
using namespace std;

int A,B,C;

int main(){
        cin >> A >> B >> C; 
        if(A == B && A == C) cout << "Yes" << endl;
        else cout << "No" << endl;
        return 0;
}


Measured memory_bytes: 256
n = int(input())
a = [int(x) for x in input().split()]
mn = 0
for i in range(n):
    if a[i] < 0:
        mn += 1
        a[i] *= -1
if mn % 2 == 1:
    print(sum(a) - 2 * min(a))
else:
    print(sum(a))

Measured memory_bytes: 64880
#include <bits/stdc++.h>
#define MAX 1005
using namespace std;

typedef long long ll;

vector<ll> a, b, c, res;

int main()
{
    int x, y, z, m;

    scanf("%d %d %d %d",  &x, &y, &z, &m);
    ll val;
    for(int i = 0; i < x; i++){
        scanf("%lld", &val);
        a.push_back(val);
    }
    for(int i = 0; i < y; i++){
        scanf("%lld", &val);
        b.push_back(val);
    }
    for(int i = 0; i < z; i++){
        scanf("%lld", &val);
        c.push_back(val);
    }

    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
    sort(c.rbegin(), c.rend());

    for(int i = 0; i < x; i++){
        for(int j = 0; j < y; j++){
            for(int k = 0; k < z; k++){
                if((i + 1) * (j + 1) * (k + 1) <= m)
                    res.push_back(a[i] + b[j] + c[k]);
                else
                    break;
            }
        }
    }

    sort(res.rbegin(), res.rend());

    for(int i = 0; i < m; i++){
        printf("%lld\n", res[i]);
    }

    return 0;
}


Measured memory_bytes: 1412