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

//AC!!!!!!

using namespace std;
const int maxn = 1e5 + 30;

int goright[maxn];

int main(){
  int n; cin >> n;
  vector<int> a;
  for(int i=0;i<n;i++){
    int t; scanf("%d", &t);
    a.push_back(t);
  }
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  for(int i = n-1; i >= 0; i--){
    if(i == n-1 || a[i] != a[i+1]) goright[i] = 0;
    else goright[i] = goright[i+1] + 1;
  }
  int x = 0;
  while(true){
    x++;
    if(a[x] <= x) break;
  }
  x--;
  assert(a[x] > x);

  /*
    If player 1 wins in either direction, then he can force things that direction.
    Otherwise, Player 2 simply steers him to (x,x) and lets him decide how he wants to lose.
  */
  if((a[x] - x) % 2 == 0){
    cout << "First\n";
  }
  else{
    if(a[x+1]-1 == x && goright[x+1] % 2 == 0){
      cout << "First\n";
    }
    else{
      cout << "Second\n";
    }
  }
}


Measured memory_bytes: 1144
n = int(input())
a = list(map(int,input().split()))

cnt = [0 for i in range(n+1)]
for val in a:
    cnt[val] += 1
    
total = 0
for l in cnt:
    total += (l*(l-1))//2

for val in a:
    print(total - cnt[val] + 1)


Measured memory_bytes: 24996
#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,pair<int,int> > c[1100];
pair<int,pair<int,int> > d[1100];
int dp[1100];
int dp2[1100];
int main(){
	int a;
	while(scanf("%d",&a),a){
		int sx,sy,tx,ty;scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
		int sz=0;
		int sz2=0;
		for(int i=0;i<a;i++){
			int x,y,r;scanf("%d%d%d",&x,&y,&r);
			if(max((sx-x)*(sx-x)+(sy-y)*(sy-y),(tx-x)*(tx-x)+(ty-y)*(ty-y))<=r*r)continue;
			if(min((sx-x)*(sx-x)+(sy-y)*(sy-y),(tx-x)*(tx-x)+(ty-y)*(ty-y))>=r*r)continue;
			if((sx-x)*(sx-x)+(sy-y)*(sy-y)<r*r)c[sz++]=make_pair(r,make_pair(x,y));
			else d[sz2++]=make_pair(r,make_pair(x,y));
		}
		std::sort(c,c+sz);
		std::sort(d,d+sz2);
		for(int i=0;i<sz;i++)dp[i]=1;
		for(int i=0;i<sz2;i++)dp2[i]=1;
		for(int i=0;i<sz;i++){
			for(int j=i+1;j<sz;j++){
				int X1=c[i].second.first;
				int Y1=c[i].second.second;
				int X2=c[j].second.first;
				int Y2=c[j].second.second;
				int R1=c[i].first;int R2=c[j].first;
				if((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)<(R2-R1)*(R2-R1))dp[j]=max(dp[j],dp[i]+1);
			}
		}
		for(int i=0;i<sz2;i++){
			for(int j=i+1;j<sz2;j++){
				int X1=d[i].second.first;
				int Y1=d[i].second.second;
				int X2=d[j].second.first;
				int Y2=d[j].second.second;
				int R1=d[i].first;int R2=d[j].first;
				if((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)<(R2-R1)*(R2-R1))dp2[j]=max(dp2[j],dp2[i]+1);
			}
		}
		int ret=0;
		for(int i=0;i<sz;i++)ret=max(ret,dp[i]);
		for(int i=0;i<sz2;i++)ret=max(ret,dp2[i]);
		for(int i=0;i<sz;i++)for(int j=0;j<sz2;j++){
			int X1=c[i].second.first;
			int Y1=c[i].second.second;
			int X2=d[j].second.first;
			int Y2=d[j].second.second;
			int R1=c[i].first;int R2=d[j].first;
			if((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)>(R2+R1)*(R2+R1))ret=max(ret,dp[i]+dp2[j]);
		}
		printf("%d\n",ret);
	}
}

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

struct sqrt_decomposition{
	using F = function<int(int, int)>;
	int n, sz, len;
	vector<int> v;
	vector<int> w;
	F f;
	int e;
	sqrt_decomposition(vector<int> _v, F _f, int _e): v(_v), f(_f), e(_e){
		n = v.size();
		sz = 1;
		while((sz+1) * (sz+1) < n) ++sz;
		len = n / sz;
		w.resize(len, e);
		for(int i=0; i<sz; ++i)
			for(int j=0; j<sz; ++j)
				if(i*sz + j < n)
					w[i] = f(w[i], v[i*sz + j]);
	}
	void point_set(int a, int x){
		v[a] = x;
		int b = a / sz;
		w[b] = e;
		for(int i=0; i<sz&&b*sz+i<n; ++i)
			w[b] = f(w[b], v[b*sz+i]);
	}
/*	void range_set(int a, int b, int x){
		while(a < b && a % sqrt_n != 0){
			v[a] = x;
			++a;
		}
		while(a + sqrt_n <= b){
			w[a / sqrt_n] = x;
			a += sqrt_n;
		}
		while(a < b){
			v[a] = x;
			++a;
		}
	}
*/	void point_operate(int a, int x){
		v[a] = f(v[a], x);
		int b = a / sz;
		w[b] = e;
		for(int i=0; i<sz&&b*sz+i<n; ++i)
			w[b] = f(w[b], v[b*sz+i]);
	}
/*	void range_operate(int a, int b, int x){

	}
*/	int point_get(int a){
		int b = a / sz;
		return f(w[b], v[a]);
	}
	int range_get(int a, int b){
		int res = e;
		while(a < b && a % sz != 0){
			res = f(res, v[a]);
			++a;
		}
		while(a + sz <= b){
			res = f(res, w[a / sz]);
			a += sz;
		}
		while(a < b){
			res = f(res, v[a]);
			++a;
		}
		return res;
	}
};

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	sqrt_decomposition sd(vector<int>(n, 0), [](int x, int y){return x+y;}, 0);
	while(q--){
		int c, x, y;
		cin >> c >> x >> y;
		if(c == 0){
			sd.point_operate(x-1, y);
		}else{
			cout << sd.range_get(x-1, y) << "\n";
		}
	}
//	for(int i=0; i<n; ++i)
//		cout << i << " " << sd.v[i] << "\n";
//	for(int i=0; i<n/sd.sz; ++i)
//		cout << i << " " << sd.w[i] << "\n";
}


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

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
        #define eprintf(...) 42
#endif

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
*/

int main()
{
  int a, b;
  cin >> a >> b;

  if(b%a == 0) cout << a+b << endl;
  else cout << b-a << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;
int doro[20][20];
int ans = 0, a, b;
int jud(int x, int y)
{
	if (x>a||y>b)return 0;
	if (doro[x][y] == 1)return 0;
	if (x == a&&y == b)return 1;

	//if(a>x&&b>y)ans+=jud(x+1,y+1);
	if (a>x)ans += jud(x + 1, y);
	if (b>y)ans += jud(x, y + 1);
	return 0;

}


int main()
{
	int num, x, y;
	while (1)
	{
		ans = 0;//初期化
		for (int i = 0; i < 20; i++)
			for (int q = 0; q < 20; q++)
				doro[i][q] = 0;

		cin >> a >> b;//道幅入力
		if (a == 0 && b == 0)break;
		cin >> num;   //障害物数
		for (int i = 0; i < num; i++)
		{
			cin >> x >> y;//障害物座標入力
			doro[x][y] = 1;
		}
		jud(1, 1);
		cout << ans << endl;
	}
	return 0;
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0515

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

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define rept(i, a, b) for(int i=a ; i<=b; i++)
    
int main(){
    int n; cin >> n;
    n %= 26;
    string s; cin >> s;
    vector<int> t;
    for(int i=0; i<(int)s.size(); i++){
        int k=(int)(s.at(i)+n);
        if(k>90) k = k%90 + 64;
        t.push_back(k);
        cout << (char)t.at(i);
    }    
        
}

                
    

Measured memory_bytes: 384
using System;

namespace a
{
    class Program
    {
        static void Main(string[] args)
        {
            var _ = Console.ReadLine().ToCharArray();
            var x = Convert.ToInt32(_[0]);
            var y = Convert.ToInt32(_[2]);

            if(x < y){
                Console.WriteLine("<");
            }else if(x > y){
                Console.WriteLine(">");
            }else{
                Console.WriteLine("=");
            }
        }
    }
}


Measured memory_bytes: 11220
#include<iostream>
const int MAX_X = 17;
const int MAX_Y = 17;
typedef std::pair<int, int> p;
int w[MAX_X][MAX_Y];
p c[41];
int main(){
	while (true){
		int a, b, n, b1, b2;
		std::cin >> a >> b;
		if (a == 0 && b == 0)break;
		std::cin >> n;
		for (int i = 0; i<a; i++){
			for (int j = 0; j<b; j++){
				w[i][j] = 0;
			}
		}
		for (int i = 0; i<a; i++){
			w[i][0] = 1;
		}
		for (int i = 0; i<b; i++){
			w[0][i] = 1;
		}
		for (int i = 0; i<n; i++){
			std::cin >> b1 >> b2;
			w[b1 - 1][b2 - 1] = -1;
		}
		bool fag = false;
		for (int i = 0; i<a; i++){
			if (fag)w[i][0] = -1;
			if (w[i][0] == -1)fag = true;
		}
		fag = false;
		for (int i = 0; i<b; i++){
			if (fag)w[0][i] = -1;
			if (w[0][i] == -1)fag = true;
		}
		for (int i = 0; i<a; i++){
			for (int j = 0; j<b; j++){
				if (i && j){
					if (w[i][j] != -1){
						if (w[i][j - 1] != -1){
							w[i][j] += w[i][j - 1];
						}
						if (w[i - 1][j] != -1){
							w[i][j] += w[i - 1][j];
						}
					}
				}
			}
		}
		std::cout << w[a - 1][b - 1] << "\n";
	}
}

Measured memory_bytes: 3092
#include <iostream>
using namespace std;
int main(void){
    int n,v,j,kari,count = 0;
    bool flag = true;
    cin >> n;
    int l[n];
    for(int i = 0; i < n; i++){
        cin >> l[i];
    }
    while(flag){
        flag = false;
        for(int j = n - 1; j >= 1; j--){
            if(l[j] < l[j - 1]){
                kari = l[j];
                l[j] = l[j - 1];
                l[j - 1] = kari;
                count++;
                flag = true;
            }
        }
    }
    for(int k = 0; k < n-1; k++){
        cout << l[k] << " ";
    }
    cout << l[n-1] << endl;
    cout << count << endl;
}
    



Measured memory_bytes: 3104
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long int ll;
using namespace std;
int main()
{
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  string ans;
  if(a + b > c +d){
    ans = "Left";
  }else if(a + b == c + d){
    ans = "Balanced";
  }else{
    ans = "Right";
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
char s[200001],t[200001];
int main()
{
	gets(s);
	gets(t);
	//scanf("%s%s",s,t);
	int i,j=0;
	for(i=0;i<strlen(s);i++){
		if(s[i]==t[i])
		continue;
		else
		j++;
	}
	printf("%d",j);
	return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
        using namespace std;
        #define int long long
const int MAX = 510000;
const int MOD = 1000000007;

     signed main(){
           int n,m;
           cin>>n>>m;
           int dp[3*n+1][n+1];
           dp[0][0]=1;for(int i=1;i<=n;i++)dp[0][i]=0;
           for(int i=1;i<=3*n;i++){
                   dp[i][0]=1;
                   for(int j=1;j<=n;j++){
                           dp[i][j]=dp[i-1][j];
                           if(i>1)dp[i][j]=(dp[i][j]+(i-1)*dp[i-2][j-1]%m)%m;
                           if(i>2)dp[i][j]=(dp[i][j]+(i-1)*(i-2)*dp[i-3][j-1]%m)%m;
                   }
           }
           int ans=0;
           for(int i=0;i<=n;i++)ans=(ans+dp[3*n][i])%m;
           cout<<ans<<endl;
         
         
}

        


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

using namespace std;


int main(){
	int n; scanf("%d",&n);
	vector<vector<int> > arr(n,vector<int>(3,0));
	for(int i = 0; i < n; i++){
		scanf("%d%d%d",&arr[i][0],&arr[i][1],&arr[i][2]);
	} 

	vector<vector<int> > dp(n, vector<int>(3,0));
	dp[0][0] = arr[0][0];dp[0][1] = arr[0][1];dp[0][2] = arr[0][2];
	for(int i = 1; i < n; i++){
		for(int j = 0; j < 3; j++){
			dp[i][j] = -1;
			for(int k = 0; k < 3; k++){
				if(k == j) continue;
				dp[i][j] = max(dp[i][j],dp[i-1][k] + arr[i][j]);
			}	
		}
	}

	cout << max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]) << endl;
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
// Hey! 僕の提出を見てくれてありがとう.
// ロボ子さん可愛いぞ！！！！！君もV沼にはまろう↓
// https://www.youtube.com/channel/UCDqI2jOz0weumE8s7paEk6g
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}//a,bの最大公約数(gcd)を求める
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}//a,bの最小公倍数(lcm)を求める
vector<ll> enum_div(ll n){vector<ll> ret;for(int i=1 ; i*i<=n ; i++){if(n%i == 0){ret.push_back(i);if(i!=1 && i*i!=n)ret.push_back(n/i);}}ret.push_back(n);return ret;}
//↑nの約数を求める
vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
//↑エラトステネスの篩で素数を求める
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend //切り上げ割り算
#define all(x) (x).begin(),(x).end() //xの初めから終わりまでのポインタ
#define size_t ll //size_tは自動でllに変換される
#define pb(x) push_back(x)
#define pri_queue priority_queue //優先度付きキュー
#define syo(x) fixed << setprecision(x) //iostreamで小数をx桁表示
//sortを降順にする時は greater<型>()
void solve(long long K){
  ll ans = 0;
  for (int i = 1; i < K+1; i++) {
    for (int l = 1; l < K+1; l++) {
      for (int n = 1; n < K+1; n++) {
        ans += gcd(i,gcd(l,n));
      }
    }
  }
  cout << ans << endl;
}

int main(){
    long long K;
	scanf("%lld",&K);
    solve(K);
}


Measured memory_bytes: 3700
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>

#ifdef PRINTERS
#include "printers.hpp"
using namespace printers;
#define tr(a)		cerr<<#a<<" : "<<a<<endl;
#else
#define tr(a)    
#endif

#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)	for(int i=a;i<b;i++)
#define dq 			v
using namespace std;

int R,C,N;
bool isGood(int x,int y){
	return x==0 or x==R or y==0 or y==C;
}
vector<pair<pii,int>>v;
void solve(){
	cin>>R>>C>>N;
	rep(i,0,N){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		if(isGood(a,b) and isGood(c,d)){
			v.pb(mp(mp(a,b),i+1));
			v.pb(mp(mp(c,d),i+1));
		}
	}
	sort(all(v),[](pair<pii,int> a,pair<pii,int> b){
		if(a.F.F==0 and b.F.F!=0)return true;
		if(a.F.F!=0 and b.F.F==0)return false;
		if(a.F.F==0 and b.F.F==0)return a.F.S<b.F.S;
		if(a.F.S==C and b.F.S!=C)return true;
		if(a.F.S!=C and b.F.S==C)return false;
		if(a.F.S==C and b.F.S==C)return a.F.F<b.F.F;
		if(a.F.F==R and b.F.F!=R)return true;
		if(a.F.F!=R and b.F.F==R)return false;
		if(a.F.F==R and b.F.F==R)return a.F.S>b.F.S;
		if(a.F.S==0 and b.F.S!=0)return true;
		if(a.F.S!=0 and b.F.S==0)return false;
		if(a.F.S==0 and b.F.S==0)return a.F.F>b.F.F;
		assert(false);
	});
	stack<int>stk;
	for(auto& i:v){
		if(stk.empty() or stk.top()!=i.S){
			stk.push(i.S);
		}
		else stk.pop();
	}
	if(stk.empty())cout<<"YES";
	else cout<<"NO";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Measured memory_bytes: 4340
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author yosiiii
 */

#include <iostream>
#include <fstream>

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

class ARedOrNot {
public:
	void solve(std::istream& in, std::ostream& out) {
        int a;
        in >> a;
        string s;
        in >> s;
        if(a>=3200){
            out << s << endl;
        }else{
            out << "red" << endl;
        }
	}
};


int main() {
	ARedOrNot solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication40
{
    class Program
    {
        static void Main()
        {
            bool[] a = { true, false, false };bool b;
            while (true)
            {
                string c = Console.ReadLine();
                if (c == null) break;
                string[] d = c.Split(',');
                Array.Sort(d);
                if (d[0] == "A")
                {
                    if (d[1] == "B") { b = a[0];a[0] = a[1];a[1] = b; }
                    else { b = a[0]; a[0] = a[2]; a[2] = b; }
                }
                else { b = a[1]; a[1] = a[2]; a[2] = b; }
            }
                 for(int u = 0; u < 3; u++)
            {
                if (a[u]) switch (u) {
                        case 0:Console.WriteLine("A"); break;
                        case 1: Console.WriteLine("B"); break;
                        case 2: Console.WriteLine("C"); break;
                    }

            }
        }
    }
}

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

#define EPS (1e-10)
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)
#define all(a) a.begin(), a.end()

using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvb = vector<vb>;

constexpr int MOD = 1000000007;

ll mod(ll x) {
    x %= MOD;
    if (x < 0) { x += MOD; }
    return x;
}

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

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

    ll ans = 0;
    rep(i, k, n + 2) {
        ll tmp = mod(i * (n - i + 1));
        ans = mod(ans + tmp + 1);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h> 
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define maxnkp make_pair
#define fi first
#define se second
#define eps 1e-6
using namespace std;
typedef long long ll;
const int mods = 1e9+7;
const int maxn = 2e5+10;
const int N = 1e5+10;
const int E = 1e6+10; 
int n;
int a[maxn];
string s,t;
map<int,int> m;

int main(){
	cin>>n;
	bool flg = 1;
	F(i,1,n) cin>>a[i];
	F(i,1,n){
		if(m[a[i]]){
			flg = 0;
			break;
		}
		m[a[i]]=1;
	}
	if(flg) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}


Measured memory_bytes: 10368
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<ll, ll>;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
using Graph = VV;
int Inf = (1 << 30);
ll inf = (1LL << 60);
const int MOD = 1e9 + 7;
int main() {
	string s;
	cin >> s;
	int n = s.size();
	for (int i = 0; i < n; i++) {
		int I = i + 1;
		if (I % 2 == 0 && s[i] == 'R') {
			cout << "No";
			return 0;
		}
		if (I % 2 != 0 && s[i] == 'L') {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

Measured memory_bytes: 256
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)
	k := getNextInt(scanner)
	hh := make([]int64, n+1)
	for i := 0; i < n; i++ {
		hh[i+1] = getNextInt64(scanner)
	}

	dp := makeInts(n+1, n+1)
	for i := 0; i <= n; i++ {
		for ii := 0; ii <= n; ii++ {
			dp[i][ii] = math.MaxInt64
		}
	}
	dp[0][0] = 0
	// dp[選択済みの数][最後に選択した高さのindex]
	for i := 1; i <= n; i++ { // 高さ
		for ii := 0; ii < i; ii++ { // 選択済みの数
			for iii := 0; iii < i; iii++ { // 最後に選択した高さのindex
				if dp[ii][iii] == math.MaxInt64 {
					continue
				}
				d := dp[ii][iii] + int64(math.Max(0, float64(hh[i]-hh[iii])))
				if dp[ii+1][i] > d {
					dp[ii+1][i] = d
				}
			}
		}
	}

	ans := int64(math.MaxInt64)
	for i := 0; i <= n; i++ {
		if ans > dp[n-k][i] {
			ans = dp[n-k][i]
		}
	}
	fmt.Fprintln(writer, ans)
	writer.Flush()
}

func makeInts(h, w int) [][]int64 {
	index := make([][]int64, h, h)
	data := make([]int64, h*w, h*w)
	for i := 0; i < h; i++ {
		index[i] = data[i*w : (i+1)*w]
	}
	return index
}


Measured memory_bytes: 1408
using System;

namespace cola2
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s_num = Console.ReadLine().Trim().Split(' ');
            if (int.Parse(s_num[0]) < int.Parse(s_num[1]) && int.Parse(s_num[1]) < int.Parse(s_num[2]))
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}

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

int main(){
while(1){
int a,b;
string op; 
cin>>a>>op>>b;

if(op == "?") break;

int A;
if(op == "+") A = a + b;
if(op == "-") A = a - b;
if(op == "*") A = a * b;
if(op == "/") A = a / b;

cout<<A<<endl;
}
return 0;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long int ll;
using namespace std;
int main()
{
  int r, g;
  cin >> r >> g;
  cout << 2*g - r<< endl;

}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public final class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] in = br.readLine().toCharArray();
		System.out.println(new Solver().solve(in));
	}

}

class Solver {

	int solve(char[] arr) {

		int pCnt = 0;
		int gCnt = 0;
		for (int i = 0; i < arr.length; i++) {

			if (arr[i] == 'g') {
				gCnt++;
			} else if (arr[i] == 'p') {
				pCnt++;
			}
		}
		return arr.length / 2 - pCnt;

	}

}

Measured memory_bytes: 23124
def main():
    def binary_search(ng, ok):
        def is_ok(mid):
            """落下するならTrue"""
            for char, drc in qs:
                if s[mid] == char:
                    mid += drc
                    if mid < 0 or mid >= n:
                        return True
            return False

        while abs(ng - ok) > 1:
            mid = (ng + ok) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    n, q = map(int, input().split())
    s = input()

    qs = []
    for _ in range(q):
        char, drc = input().split()
        drc = -1 if (drc == 'L') else 1
        qs.append((char, drc))
        # char:指定マス文字,英大文字
        # drc:方向,L=-1,R=1

    mid = n // 2
    left = binary_search(ng=mid + 1, ok=-1)  # okを返すので、最大mid
    right = binary_search(ng=mid, ok=n)  # okを返すので、最小mid+1
    # ok=落下する境目（落下側）
    # oolxxxroo -> r-1-l=6-1-2=3=xの個数
    # 012345678

    print(right - 1 - left)


if __name__ == '__main__':
    main()


Measured memory_bytes: 17840
#include<cstdio>
#include<cmath>
int main()
{
	int N,T[105],M,P[105],X[105],sum=0,cnt;
	scanf("%d",&N);
	for(int i=1; i<=N; i++)
	{
		scanf("%d",&T[i]);
		sum+=T[i];
	}
	scanf("%d",&M);
	for(int i=1; i<=M; i++)
	scanf("%d%d",&P[i],&X[i]);
	for(int i=1; i<=M; i++)
	{
		cnt=sum-T[P[i]]+X[i];
		printf("%d\n",cnt);
	}
	 
	return 0;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  if((s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3]))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

}


Measured memory_bytes: 256
import itertools

n,m,q = map(int, input().split(" "))
a,b,c,d = [],[],[],[]
for i in range(q):
  inpu = input()
  a.append((int)(inpu.split(" ")[0]))
  b.append((int)(inpu.split(" ")[1]))
  c.append((int)(inpu.split(" ")[2]))
  d.append((int)(inpu.split(" ")[3]))

balls = list(itertools.combinations_with_replacement(range(1, m + 1), n))
#print(balls)
max = 0
for i in range(len(balls)):
  temp = 0
  for j in range(q):
    if balls[i][b[j] - 1] - balls[i][a[j] - 1] == c[j]:
      temp += d[j]
  if temp > max:
    max = temp
print(max)

Measured memory_bytes: 84676
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;
import java.awt.Point;

public class Main {
    // static int INF = (1 << 30) - 1;
    // static long L_INF = (1L << 62) - 1;
    // static long MOD = (long) 1e9 + 7;

    static class Solver {
        int N, W;
        int[] v, w;

        // write your code
        void solve(InputReader in, PrintWriter out) {
            N = in.nextInt();
            W = in.nextInt();
            v = new int[N];
            w = new int[N];
            for (int i = 0; i < N; i++) {
                v[i] = in.nextInt();
                w[i] = in.nextInt();
            }

            int[] dp = new int[W + 1];
            Arrays.fill(dp, -1);
            dp[0] = 0;
            for (int i = 0; i < N; i++) {
                for (int j = W; j >= 0; j--) {
                    if (dp[j] != -1 && j + w[i] <= W) {
                        dp[j + w[i]] = Math.max(dp[j + w[i]], dp[j] + v[i]);
                    }
                }
            }
            int ans = 0;
            for (int i = 0; i < W + 1; i++) {
                ans = Math.max(ans, dp[i]);
            }
            out.println(ans);
        }

        void debug(Object... os) {
            System.err.println(Arrays.deepToString(os));
        }
    }

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(in, out);
        out.close();
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}



Measured memory_bytes: 25684
array_first = []
array_second = []
array_turns = []

input_str = input()

while True:
    turns = int(input_str)

    if turns == 0:
        break

    array_turns.append(turns)

    for turn in range(turns):
        input_str = input()

        first = ''
        second = ''

        flag_space = False
        for i in range(len(input_str)):
            if input_str[i] == ' ':
                flag_space = True
                continue
            if not flag_space:
                first += (input_str[i])
            else:
                second += (input_str[i])

        array_first.append(int(first))
        array_second.append(int(second))

    input_str = input()

scores_first = []
scores_second = []
passed_turns = 0

for turns in array_turns:
    score_first = 0
    score_second = 0

    for turn in range(turns):
        if array_first[turn + passed_turns] > array_second[turn + passed_turns]:
            score_first += array_first[turn + passed_turns] + array_second[turn + passed_turns]
        elif array_first[turn + passed_turns] < array_second[turn + passed_turns]:
            score_second += array_first[turn + passed_turns] + array_second[turn + passed_turns]
        else:
            score_first += array_first[turn + passed_turns]
            score_second += array_second[turn + passed_turns]

    scores_first.append(score_first)
    scores_second.append(score_second)
    passed_turns += turns

for idx, score in enumerate(zip(scores_first, scores_second)):
    print(score[0], score[1])



Measured memory_bytes: 5984
while True:
    a, op, b = input().split()   
    a =int(a)                   
    b = int(b)                   


    if op=="?": 
        break
    else:    
        if op=="+":
            print(a+b)
        elif op=="-":
            print(a-b)
        elif op=="*":
            print(a*b)
        elif op=="/":
            print(a//b)
    



Measured memory_bytes: 5592
#include<bits/stdc++.h>
#include<ctype.h>
# define pb push_back
#define fst first
#define sec second
#define For(i,a,b) for(int i=a;i<b;i++)
#define ll long long int
#define ull unsigned long long int
#define mod 1000000007
#define fo(i,n) for(ll i=0;i<n;i++)
#define endl "\n"
#define rev(i,n) for(ll i=n-1;i>=0;i--)
#define fo1(i,n) for(ll i=1;i<=n;i++)
#define boolsize 1000001
#define pi pair<ll,ll>
#define vi vector<ll>
#define vii vector<pi>
using namespace std;
template<typename T>
void showvector(vector <T> v)
{
    for(T x:v)
        cout<<x<<" ";
    cout<<endl;

}
template<typename T>
void showvector1(vector <T> v)
{
    ll n=v.size();
    fo1(i,n-1)
        cout<<v[i]<<endl;

}
template<typename T>
void showset(set <T> s)
{
    for(T x: s)
        cout<<x<<" ";
    cout<<endl;
}
template<class T>
void showvectorpair(vector<T> v)
{
    for(auto it=v.begin();it!=v.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    cout<<endl;
}
template<typename T,typename P>
void showmap(map <T,P> m)
{
    for(auto it=m.begin();it!=m.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    cout<<endl;
}
template<typename T>
bool comp(T a,T b)
{
    return (a>b);
}
template<class T>
bool comppair(T a,T b)
{
    if(a.first==b.first)
        return(a.second>b.second);
    return (a.first>b.first);
}
bool sameparity(ll a,ll b)
{
    return (a%2==b%2);
}
bool difparity(ll a,ll b)
{
    return !(a%2==b%2);
}
bool isprime(ll x)
{   if(x<=1)
     return false;
    for(ll i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
            return false;
    }
    return true;
}
bool iseven(ll x)
{
    return !(x%2);
}
bool isodd(ll x)
{
    return (x%2);
}
//vector <bool> prime(boolsize,1);
//void seive()
//{
//    ll n=boolsize;
//    prime[0]=prime[1]=0;
//    for(ll i=2;i<=sqrt(boolsize);i++)
//    {
//        if(prime[i]==1)
//        {
//            for(ll j=i*i;j<=n;j+=i)
//            {
//                prime[j]=0;
//            }
//        }
//    }
//}

/// check for test case before submitting
void vfun()
{
 string s,a,b;
 cin>>s;
 if(s.size()%2)
    s.pop_back();
 else
 {
     s.pop_back();s.pop_back();
 }
 while(!s.empty())
 {
     ll k=s.size()/2;
     a.assign(s.begin(),s.begin()+k);
     b.assign(s.begin()+k,s.end());
     if(a==b)
        break;
     s.pop_back();
     s.pop_back();
 }
 cout<<2*a.size();

}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0); ///cant use scanf, printf
    cin.tie(0);cout.tie(0); /// no longer auto flush cout before each cin, remove for interactive
    //cout << fixed << setprecision(11); /// no scientific output
    ll test=1;
    //cin>>test;
    while(test--)
    {

        //fun();
        vfun();
//         if(vfun())
//            cout<<"YES\n";
//         else
//            cout<<"NO\n";
    }
}
///before sub
/// check for value of zero and single input in array
///loop vars,1LL in mult, equal, one, bounds, int v ll, endl, finish taking inputs
/// check whether test cases are given or not




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

using namespace std;

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

   string s;
   cin>>s;
    if(s[3]==s[2] && s[5]==s[4]) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
n = int(input())
b = list(map(int, input().split()))

a = [0] * n

a[0] = b[0]
a[-1] = b[-1]
for i, (v1, v2) in enumerate(zip(b[:-1], b[1:]), 1):
    a[i] = min(v1, v2)

print(sum(a))


Measured memory_bytes: 3060
import copy

n=int(input())
f1=list(map(int,input().split()))
f2=copy.deepcopy(f1)
c=0
for i in range(n-1):
    if f1[i]==i+1:
        c+=1
        f1[i],f1[i+1]=f1[i+1],f1[i]

for i in range(n-1,0,-1):
    #print(d)
    if f1[i]==i+1:
        c+=1
        f1[i],f1[i-1]=f1[i-1],f1[i]

print(c)


Measured memory_bytes: 14324
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<numeric>
#include<vector>
#include<tuple>
using namespace std;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
typedef long long ll;
const int MOD = 1e9 + 7;
double N,T,near=10000,A;
int ans = 0;
double H[10000];


int main(void)
{
	cin >> N>>T>>A;
	FOR(i, 0, N) {
		cin >> H[i];
		double s = T - H[i] * 0.006;
		if (abs(A-s) < near) {
			ans = i + 1;
			near = abs(A-s);
		}
	}
	ct(ans);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define inf 1e9+7
#define ll long long
#define clr(c) memset(c,0,sizeof(c))
const int M=2e5+10;
const int N=1e5+10;
using namespace std;
inline ll read()
{
	ll sum=0,b=1; char c=getchar();
	while(!isdigit(c)){if(c=='-') b=-1; c=getchar();}
	while(isdigit(c)){sum=sum*10+c-48; c=getchar();}
	return b*sum;
}
ll n,m,b,k;
char s[110];
ll q_pow(ll x,ll y)
{
	ll t=x,res=1;
	while(y)
	{
		if(y&1) res=res*t;
		t*=t;
		y>>=1;
	}
	return res;
}
int main()	
{	
	ll i,j;
	scanf("%s",s+1);
	k=read();
	ll ans=0;
	ll len=strlen(s+1);
	ll l=0,r=0,rr=0;
	for(i=2;i<=len;i++)
	{
		if(s[i]!='0')
		{
			if(l==0) l=i;
			else if(r==0) r=i;
			else if(rr==0) {rr=i;break;}
		}
	}
	if(k==1)
	{
		ll x=s[1]-'0';
		ans=x+(len-1)*9;
	}
	else if(k==2)
	{
		if(len==1)
		{
			printf("0"); return 0;
		}
		ll x=s[1]-48,y=max(s[l]-48,0),z=max(s[r]-48,0);		
		ans=(x-1)*9*(len-1)+81*(len-1)*(len-2)/2;//最高位为0  
		if(l>0)
		{
			ans+=y;//最高位不变，次高位乱选			
			ans+=9*(len-l);
		}
	}
	else if(k==3)
	{
		if(len<3)
		{
			printf("0"); return 0;
		}
		ll x=s[1]-48;
		ll y=max(s[l]-48,0),z=max(s[r]-48,0),zz=max(s[rr]-48,0);		
		ans=(x-1)*81*(len-2)*(len-1)/2+81*9*(len-1)*(len-2)*(len-3)/6;//最高位为0 和小于 
		if(l>0)
		{
			if(r>0)
			{
				ans+=z+9*(len-r);
				//此高位同	
			}
			ans+=(y-1)*9*(len-l)+81*(len-l)*(len-l-1)/2;//此高位不同 
		}
	}
	
	
	printf("%lld",ans);
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, A, B;
  cin >> N >> A >> B;
  string S;
  cin >> S;
  int b_count = 0;
  int count = 0;
  for(int i = 0; i < S.size(); i++) {
    if(S.at(i) == 'a') {
      if(count < A + B) {
        cout << "Yes" << endl;
        count++;
      }
      else {
        cout << "No" << endl;
      }
    }
    else if(S.at(i) == 'b') {
      b_count++;
      if(count < A + B && b_count <= B) {
        cout << "Yes" << endl;
        count++;
      }
      else {
        cout << "No" << endl;
      }
    }
    else {
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 3732
function partition(nums,p,r){
    let base = nums.slice(-1);
    let i=p-1;
    for(let j=p;j<r;j++){
        if(nums[j]<=base){
            i++;
            let temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    let temp = nums[i+1];
    nums[i+1] = "["+nums[r]+"]";
    nums[r] = temp;
    return nums;
    
    
    
}

let nums = require("fs").readFileSync("/dev/stdin","utf-8").trim().split("\n")[1].split(" ").map(Number);
console.log(partition(nums,0,nums.length-1).join(" "));


Measured memory_bytes: 32616
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
    int k, q; cin>>k>>q;
    ll d[5050];
    for(int i=0; i<k; i++) cin>>d[i];
    while(q--){
        ll n, x, m;
        cin>>n>>x>>m;
        ll e[5050];
        x%=m;
        ll s=0, t=0;
        ll cnt=0, cnt1=0;
        for(int i=0; i<k; i++){
            e[i]=d[i]%m;
            if(e[i]==0) cnt++;
            if(e[i]==0 && i<(n-1)%k) cnt1++;
            s+=e[i];
            if(i<(n-1)%k) t+=e[i];
        }
        x+=s*((n-1)/k)+t;
        x/=m;
        cout<<n-1-x-cnt*((n-1)/k)-cnt1<<endl;
    }
    return 0;
}


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

int sort(const void *a, const void *b){
    return *(int*)b-*(int*)a ;
}

int main(void){
    int n;
    scanf("%d",&n);
    int a[n*3];
    for (int i=0; i<n*3; i++){
        scanf("%d",&a[i]);
    }
    long long ans=0;
    qsort (a,n*3,sizeof(int),sort);
    for (int i=0; i<n; i++){
        ans+=a[i*2+1];
    }
    printf ("%lld\n",ans);
	return 0 ;
}

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

int main(void){
    string x;
    cin >> x;
    if(x.at(0)!=x.at(1) && x.at(1)!=x.at(2) && x.at(2)!=x.at(0))
        cout << "Yes" << endl;
    else cout << "No" << endl;
}


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

int main() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (i + 1 < n && s[i] == s[i + 1]) {
            printf("%d %d\n", i+1, i + 2);
            return 0;
        } else if (i + 2 < n && s[i] == s[i + 2]) {
            printf("%d %d\n", i+1, i + 3);
            return 0;
        }
    }
    puts("-1 -1\n");
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for(int i=0;i<(int)n;i++)
#define PI acos(-1)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
ll mod=1e9+7;

int main(){
    fast_io

    int n,m,k;
    cin>>n>>m>>k;

    for(int i=0;i<=m;i++){
        for(int j=0;j<=n;j++){
            if(j*m+i*n-2*i*j == k){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
    return 0;

}


Measured memory_bytes: 256
N = int(input())
P = list(map(int,input().split()))
c = 0

for n in range(N-1):
  if P[n]==n+1:
    P[n],P[n+1] = P[n+1],P[n]
    c+=1

if P[-1]==N:
  print(c+1)
else:
  print(c)

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

int main(){

int n,cnt=0;
 string s;
 cin>>n;
 cin>>s;

 for(int i=0; i<=s.length()-2; i++){
    if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C')
        cnt++;
 }
 cout<<cnt;

}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i =(b)-1;i>=(a);--i)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
typedef vector<int> vi;
const int mod = 1e9 + 7;
const int maxn = 2e6 + 10;
int f[(1 << 9) + 10][100010];
int v[(1 << 18) + 10],w[(1 << 18) + 10]; 
int dfs(int x,int ws){
	if(x < (1 << 9))return f[x][ws];
	if(w[x] <= ws)
		return max(dfs(x/2,ws),dfs(x/2,ws-w[x]) + v[x]);
	return dfs(x/2,ws);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,q;
	cin >> n;
	rep(i,1,n+1)cin >> v[i] >> w[i];
	rep(i,1,min(n+1,1<<9)){
		rep(j,0,1e5+1){
			f[i][j] = f[i/2][j];
			if(j >= w[i])
				f[i][j] = max(f[i][j],f[i/2][j - w[i]] + v[i]);
		}
	}
	int query,weight;
	cin >> q;
	rep(i,0,q){
		cin >> query >> weight;
		if(query < (1<<9)){
			cout << f[query][weight] << '\n';
		}
		else{
			cout << dfs(query,weight) << '\n';
		}
	}
	return 0;
}


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

int main()
{
    int d,t,s;
    double ttt;
    scanf("%d%d%d",&d,&t,&s);
    ttt=(d*1.00)/s;
    if(ttt<=t)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }



    return 0;
}


Measured memory_bytes: 1644
#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<ll,ll> P;
const ll MOD=1234567;
const ll INF=1000000010;
const ll LINF=1000000000000000010LL;
const int MAX=500010;
const double EPS=1e-3;
int dx[4]={0,1,0,1};
int dy[4]={0,0,1,1};
//最大公約数
ll gcd(ll m,ll n){
    if((0==m)||(0==n)){
        return 0;
    }
    if(m<n){
        swap(m,n);
    }
    ll r=m%n;
    while(r!=0){
        m=n;
        n=r;
        r=m%n;
    }
    return n;
}
//最小公倍数
ll lcm(ll m,ll n){
    if((0==m)||(0==n)){
        return 0;
    }
    return ((m/gcd(m,n))*n);
}
int main(){
	ll a,b;
	while(cin>>a>>b){
		cout<<gcd(a,b)<<" "<<lcm(a,b)<<endl;
	}
	return 0;
}



Measured memory_bytes: 3096
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define re register
using namespace std;
struct ios{
	inline char fchar(){
		static char buf[100000],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
	}
//	#define getchar fchar
	template <typename ty> inline ios& operator >> (ty &x)
	{
		register int f=1;x=0;register char c=getchar();
		for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
		for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
		x*=f;return *this;
	}
	template <typename ty>  inline ios& operator << (ty x)
	{
		if(x<0) x=-x,putchar('-');
		if(x>9) *this << x/10;
		putchar(x%10+48);
		return *this;
	}
	inline ios& operator << (char x){putchar(x);return *this;}
}io;
const int N = 100;
int n;
int a[N];
int main()
{
	io>>n;
	int cnt=0;
	for(int i=1;i<=n;i++) io>>a[i];
	int flag=1;
	for(int i=1;i<n;i++) if(a[i]>a[i+1]) flag=0;
	if(flag){puts("YES");return 0;}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			swap(a[i],a[j]);
			int flag=1;
			for(int k=1;k<n;k++) if(a[k]>a[k+1]) flag=0;
			if(flag){puts("YES");return 0;}
			swap(a[i],a[j]);
		}
	}
	puts("NO");	
    return 0;
}

Measured memory_bytes: 128
N, A, B, C, D = map(int,input().split())
S = 'd' + input()

OK = True
if A < C < B < D or A < B < C < D:
    if S[A:C+1].count("##") == 0 and S[B:D+1].count("##") == 0:
        pass
    else:
        OK = False
else:
    if S[A:C+1].count("##") == 0 and S[B:D+1].count("##") == 0 and S[B-1:D+2].count("...") > 0:
        pass
    else:
        OK = False
if OK:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3636
#include "bits/stdc++.h"

typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) {
    if (a < b) swap(a, b);
    ll r = a % b;
    while (r) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main() {
    int n, X;
    cin >> n >> X;
    vector<int> x(n + 1);

    x[0] = X;
    for (int i = 0; i < n; ++i) cin >> x[i + 1];
    sort(x.begin(), x.end());

    int ans = x[1] - x[0];
    for (int i = 1; i < n; ++i) {
        ans = gcd(ans, x[i + 1] - x[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define INF 1<<50LL
#define fst first
#define snd second
#define pb push_back
#define int long long
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define debug(x)  cout << #x << " = " << (x) << endl;
typedef long long ll;
typedef pair<ll,ll> P;

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

  string s;
  cin >> s;
  
  int ans = s.size(),i = 0,cnt = 0;
  
  REP(i,s.size()){
    if(s[i] == 'S') cnt++; 
    if(s[i] == 'T' && cnt > 0){
      ans -= 2;
      cnt--;
    }
  }
  
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 720
N,Q = map(int,input().split())
BIT = [0]*(N+1)

def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**12+l*10**6+q)
queries.sort()

curR = 0
for i in range(Q):
    query = queries[i]
    r = query//10**12
    query %= 10**12
    l = query//10**6
    q = query % 10**6
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Measured memory_bytes: 166496
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll a,b,c;
    cin >> a >> b >> c;
    ll ans = b+min(c,a+b+1);
    cout<<ans<<"\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define print(a,n)  for(lli i=0;i<n;i++)cout<<a[i]<<' ';br
#define br          cout<<endl;
#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define f           first
#define s           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define upar        1000000007
#define fr(i,a,b)   for(int i=a;i<=b;i++)
#define tez         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

int a[1000005];
int b[1000005];
void solve()
{
int n;
cin>>n;
fr(i,1,n)
{

    cin>>a[i];
}
fr(i,1,n)
{
    b[a[i]]=i;
}
fr(i,1,n)
{
    cout<<b[i]<<" ";
}
}


signed main() {

  tez;
  int t = 1;
  // cin>>t;
  while (t--) {
    solve();
  }
  return 0;
}

Measured memory_bytes: 5760