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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define pb push_back
#define pf push_front
#define mod 1000000007
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK puts("OK")
#define OK1 puts("OK1")
#define OK2 puts("OK2")
#define SIZE(s) (int)s.size()
#define Cout(n) cout<<(n)<<endl
#define INF 1000000000000000000LL

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;
typedef vector<string> vs;
const double pi = acos(-1.0);

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }

int main()
{
	string s;
	cin >> s;
	rep(i,SIZE(s)) cout << 'x';
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
//DP Contest

  #include<bits/stdc++.h>
  using namespace std;
  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define endl "\n"
  #define ll long long
  #define int long long
  #define double long double
  #define max(a,b) (a>b?a:b)
  #define min(a,b) (a<b?a:b)
  #define mp make_pair
  #define pb push_back
  #define inf INT_MAX
  #define f first
  #define s second
  #define all(v) v.begin(), v.end()
  #define mod INT_MAX 
  const int MOD=1e9+7;
//Ques J: Sushi
  //Constraints on N is small N=300
  //can hint that dp or solution dimensions or runtime maybe huge,O(N^3) or more
  //Need: Ans=EXPECTED NUMBER OF THROWS BEFORE ALL DISHES ARE EMPTY
  //what matters? number of dishes & number of sushi's in that dish, at that point
  //(num of sushi is between [1,3] in a dish)


  //dp[i][j][k]= number of 1s,2s, n 3s in that dp state

const int M=305;
double dp[M][M][M],ev[M][M][M];
//ev[a][b][c] is the expected number of die throws to get to the state (a,b,c)
//easier is to get the prob of getting to the state(a,b,c)
//so we calculated that first


  int32_t main()
  {
  	IOS
    int n,x;
    cin>>n;
    vector<int> cnt(4,0);
    for (int i = 0; i < n; ++i)
    {
    	
    	cin>>x;
    	cnt[x]++;
    }

    dp[cnt[1]][cnt[2]][cnt[3]]=1;

//here again it is top-down dp
    //we are going to states that would have come before,
    //to cross check print n see dp[0][0][0]=1; we are sure to reach that state, sometime
    //others may or may not be always achievable


    for(int c=n;c>=0;c--)
    {
    	for(int b=n;b>=0;b--)
    	{
    		for(int a=n;a>=0;a--)
    		{
    			if(a==0 && b==0 && c==0) continue;
    			if((a+b+c)> n) continue;
    			//dp[a][b][c] is the sushi states

    			//p_waste is the prob of wasting an operation on the empty plates
    			double p_waste=(double)(n-(a+b+c)) / n;
    			//expectation of p_waste is a GP sum
    			//p_waste + p_waste^ 2 +.....=S
    			//1+S=S/p_waste

    			double ev_pwaste=p_waste/(1-p_waste) +1; //+1 because i also need to move to 
    			//some other state!
                ev[a][b][c]+=ev_pwaste*dp[a][b][c];

    			if(a!=0){
    				//p_going to that state = a/(a+b+c)
    			dp[a-1][b][c]+=dp[a][b][c] * a/(a+b+c);
    			ev[a-1][b][c]+=ev[a][b][c] * (double) a/(a+b+c);
                }
    			if(b!=0) {//if num of 2 decreases, num of 1 states increases
    			dp[a+1][b-1][c]+=dp[a][b][c] * b/(a+b+c);
    			ev[a+1][b-1][c]+=ev[a][b][c] * (double) b/(a+b+c);
    		    }

    			if(c!=0){
    			dp[a][b+1][c-1]+=dp[a][b][c] * c/(a+b+c);
    			ev[a][b+1][c-1]+=ev[a][b][c] * (double) c/(a+b+c);
    			}
    		}
    	}
    }
    cout<<fixed<<setprecision(10)<<ev[0][0][0];

 return 0;
}

Measured memory_bytes: 874752
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)

dp = [[0]*n for i in range(2**n)]
dp[1][0] = 1

for s in range(2**n):
    for v in range(n):
        if (s >> v) & 1:
            # t = s - {v}
            t = s ^ (1 << v)
            for u in g[v]:
                if (t >> u) & 1:
                    dp[s][v] += dp[t][u]
#print(dp)
ans = 0
for v in range(n):
    ans += dp[-1][v]
print(ans)

Measured memory_bytes: 80072
s = input()

n = int(s)

numbers = []
answer = 0
check = True

v  =input().split()

for i in range(n):
    numbers.append(int(v[i]))

while (check):
    for i in range(len(numbers)):
        if numbers[i] % 2 == 1:
            check = False
        else:
            numbers[i] /= 2
    if check:
        answer += 1

print(answer)




Measured memory_bytes: 9048
#include <iostream>
using namespace std;
int Min = -1;
int n;
int a, b, c;
int q[8];
int l[8];

void dfs (int x ) {
  if (x <= n - 1) {
    for (int i = 0; i < 4; i++) {
      q[x] = i;
      dfs(x + 1);  
    }  
  }  
  else {
    int sum[3];
    for (int i = 0; i < 3; i++) { 
      sum[i] = 0;  
    }
    int sub = 0;
    for (int i = 0; i < n; i++) {
       if (q[i] < 3) {
        if (sum[q[i]] > 0) {
            sub += 10;
            sum[q[i]] += l[i]; 
        }  
        else {
          sum[q[i]] += l[i];  
        }
       }
    } 
    if (sum[0] > 0 && sum[1] > 0 && sum[2] > 0) {
      sub = sub + abs(a - sum[0]) + abs(b - sum[1]) + abs(c - sum[2]);
      if (Min == -1 || sub < Min ) {
        Min = sub;  
      }     
    }
  }
}

int main () {
  cin >> n >> a >> b >> c;
  for (int i = 0; i < n; i++) {
    cin >> l[i];
    q[i] = -1;  
  }  
  dfs (0);
  cout << Min << endl;
}

Measured memory_bytes: 256
n, m, l = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
b = [list(map(int, input().split())) for i in range(m)]

c = [[0] * l for i in range(n)]
for i in range(n):
    for j in range(l):
        for k in range(m):
            c[i][j] += a[i][k] * b[k][j]
    print(*c[i])



Measured memory_bytes: 7032
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
using namespace std;

#define rep(i, s) for (int i = 0; i < s; ++i)
#define all(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    int n;
    cin>>n;
    priority_queue<ll, vector<ll>, greater<ll> >que1; //小さい順に並べた。n~2nまでの大きさを取りうる。
    priority_queue<ll> que2;//大きい順に並べた。
    vector<ll>a(3*n);//aは3*n個の与えられた値を持つ配列。
    for(int i=0;i<3*n;i++){
        cin>>a.at(i);
    }
    for(int i=0;i<n;i++){
        que1.push(a.at(i));//que1は前からn+k個の大きい値n個を所持。まずは、左のn個の値を優先度付きで所持。
        que2.push(a.at(3*n-1-i));
    }
    vector<ll>que_1(n+1,0);//que_1は前からn+k個の大きい値n個の和を所持。
    vector<ll>que_2(n+1,0);

    //まず、que_1[0]に、初めのn個の和を入れておく。
    //que_2[0]に後ろのn個の和を入れておく。
    for(int i=0;i<n;i++){
        que_1.at(0)+=a.at(i);
        que_2.at(0)+=a.at(3*n-1-i);
    }
    for(int i=0;i<n;i++){
        que1.push(a[n+i]);//この操作でque1には、前からn+k個の大きい値n個を所持を実現。
        que2.push(a[2*n-1-i]);
        que_1.at(i+1)=que_1.at(i)+a[n+i]-que1.top();
        que1.pop(); //n個の中身を保つためにpopする
        que_2.at(i+1)=que_2.at(i)+a[2*n-1-i]-que2.top();
        que2.pop();
    }
    ll MAX=que_1.at(0)-que_2.at(n);
    // cout<<MAX<<endl;
    for(int i=0;i<que_1.size();i++){
        MAX=max(MAX,que_1.at(i)-que_2.at(n-i));
        // cout<<que_1.at(i)<<"AAA"<<que_2.at(n-i)<<endl;
        // cout<<que_1.at(i)-que_2.at(n-i)<<endl;
        // cout<<"MAX:"<<MAX<<endl;
    }
    cout<<MAX<<endl;


    return 0;
}

Measured memory_bytes: 5996
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
#include <queue>
#include <stack>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(long long int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

class Graph{
public:

Graph(long long int o_size){
    graph_size=o_size;
    node.resize(graph_size,0);
    edge.resize(graph_size);
}

long long int add_edge(long long int a,long long int b){
    edge[a].push_back(b);
    edge[b].push_back(a);
        
    return a+b;
}

long long int node_add(long long int i,long long int a){
    node[i]+=a;
    return node[i];
}

void dfs(long long int start){
    stack<pair<long long int,long long int>> st;
    st.push(make_pair(-1,start));
    while(st.size()){
        long long int where = st.top().second,pre_where=st.top().first;
        //cout << "Unko" << endl;
        st.pop();
        node[where]++;
        //cout << where << endl;
        for(auto x:edge[where]){
            if(x!=pre_where&&node[x]==0){
                st.push(make_pair(where, x));
               
            }
        }
        
    }

}

void print(long long int n){
REP(i,n){
    if(node[i]==0){
        cout << "NO" << endl;
        return;
    }
}
cout << "YES" << endl;
}


private:
vector<vector<long long int>> edge;
vector<long long int> node;
long long int graph_size;

};

int main(){

    long long int n,m,tmpa,tmpb;
    cin>>n>>m;
    Graph graph(n+m);
    REP(i,n){

        scanf("%lld",&tmpa);
        REP(j,tmpa){
            scanf("%lld", &tmpb);
            graph.add_edge(i,n+tmpb-1);
        }
    }

    graph.dfs(0);
    graph.print(n);

    return 0;
}


Measured memory_bytes: 12020
#include<bits/stdc++.h>
using namespace std;
long long INF = numeric_limits<long long>::max()/4;
long long dp[303][303];
int n,m,l;


int main(){
	cin>>n>>m>>l;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(i==j) dp[i][j] = 0;
			else dp[i][j] = INF;
		}
	}
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		dp[a][b] = dp[b][a] = c;
	}
	for(int k=1; k<=n; k++){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(i==j) dp[i][j] = INF;
			else if(dp[i][j]<=l) dp[i][j] = 1;
			else dp[i][j] = INF;
		}
	}
	for(int k=1; k<=n; k++){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
	int q;
	cin>>q;
	while(q--){
		int start,des;
		cin>>start>>des;
		if(dp[start][des]==INF) cout<<-1<<'\n';
		else cout<<dp[start][des]-1<<'\n';
	}
}

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

dp = [[0,0] for _ in range(42)]

for i in range(1,42):
    if dp[i-1][1] == 1:
        dp[i][1] = 1

    ctr = 0
    for j in range(n):
        if (a[j]>>(41-i))&1 == 1:
            ctr += 1

    if ctr >= n-ctr:
        dp[i][0] = dp[i-1][0] + ctr*(2**(41-i))
        if (k >> (41-i))&1 == 1:
            dp[i][1] = 1
    else:
        if dp[i][1] == 1:
            dp[i][0] = dp[i-1][0]+(n-ctr)*(2**(41-i))
        else:
            if (k >> (41-i))&1 == 1:
                dp[i][0] = dp[i-1][0]+(n-ctr)*(2**(41-i))
            else:
                dp[i][0] = dp[i-1][0] + ctr*(2**(41-i))

print(dp[41][0])

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

const ll MAXN = 200000;
const ll INF = 1001001001;

ll N, M, R, ans=0, tmp=0;
vector<ll> Rs;
vector<vector<ll>> D;

signed main(){
    cin >> N >> M >> R;
    Rs.resize(R);
    D.resize(N);
    for(int i=0;i<N;i++) {
        D[i].resize(N, INF);
        D[i][i] = 0;
    }
    for(int i=0;i<R;i++) {
        cin >> Rs[i];
        Rs[i]--;
    }
    //cout << "OK" << endl;
    for(int i=0;i<M;i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        D[a][b] = c;
        D[b][a] = c;
    }
    //cout << "OK" << endl;
    for(int k=0;k<N;k++) {
        for(int i=0;i<N-1;i++) {
            for(int j=i+1;j<N;j++) {
                D[i][j] = min(D[i][j], D[i][k]+D[k][j]);
                D[j][i] = D[i][j];
            }
        }
    }
    //cout << "OK" << endl;
    vector<int> v;
    for(int i=0;i<min(R,min(8LL, N));i++) {
        v.push_back(i);
    }
    ans = INF;
    do {
        tmp = 0;
        for(int i=0;i<min(R,min(8LL, N))-1;i++) {
            tmp += D[Rs[v[i]]][Rs[v[i+1]]];
        }
        ans = min(ans, tmp);
    } while (next_permutation(v.begin(), v.end()));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
require 'scanf'
require 'matrix'

while str = STDIN.gets
    x1,y1,x2,y2,x3,y3,xp,yp=\
        str.scanf("%f %f %f %f %f %f %f %f") 
    v1=Vector[x2-x1,y2-y1]
    v2=Vector[x3-x1,y3-y1]
    vp=Vector[xp-x1,yp-y1]
    mat=Matrix[v1,v2]
    ans=Matrix[vp]/mat
    if 0<ans[0,0] and ans[0,0]<1.0 and \
        0<ans[0,1] and ans[0,1]<1.0 and \
        0<ans[0,0]+ans[0,1] and ans[0,0]+ans[0,1]<1.0 then
        print "YES\n"
    else
        print "NO\n"
    end
end

Measured memory_bytes: 8680
n, d, a = map(int, input().split())
xh = []
for _ in range(n):
    x, h = map(int, input().split())
    h = (h - 1) // a + 1
    xh.append([x, h])
xh.sort()
damage = xh[0][1]
ans = damage
damage_lst = [[xh[0][0] + d * 2, damage]]
pos = 0
for i, (x, h) in enumerate(xh[1:], start = 1):
    while x > damage_lst[pos][0]:
        damage -= damage_lst[pos][1]
        pos += 1
        if pos == i:
            break
    damage_tmp = max(h - damage, 0)
    ans += damage_tmp
    damage += damage_tmp
    damage_lst.append([x + d * 2, damage_tmp])
print(ans)

Measured memory_bytes: 71004
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 2000010;

int n,m,T;
ll a[maxn];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    if(n==1)return cout<<a[0]<<endl,0;
    sort(a,a+n);
    ll ans=0;
    ans=a[1]/__gcd(a[0],a[1])*a[0];
    for(int i=2;i<n;i++)
        ans=max(ans,a[i])/__gcd(a[i],ans)*min(ans,a[i]);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <unistd.h>
#include <stdlib.h>

void writing(int ans)
{
    char c;
    if (ans < 10)
    {
        c = ans + '0';
        write(1, &c, 1);
    }
    else
    {
        writing(ans / 10);
        writing(ans % 10);
    }
}

void get_nums(int *array, char *s, int count)
{
    int num;
    int i;
    
    i = -1;
    while (s[++i] != 10)
    {
        if (s[i] != 32)
        {
            num = 0;
            while ('0' <= s[i] && s[i] <= '9')
            {
                num = num * 10 + s[i++] - '0';
                if (!s[i])
                {
                    array[count++] = num;
                    return ;                    
                }
            }
            array[count++] = num;
            i--;
        }
    }  
}

void get_num_plus(int *num, char *tmp, int pass_flag, int count)
{
    int i;
    
    i = -1;
    while (count < pass_flag)
    {
        while (tmp[++i] != 10)
            ;
        count++;
    }
    get_nums(num, &tmp[++i], 0);
}

void get_ans(int a, int b, char *tmp)
{
    int ans[a];
    int num[2];
    int i;
    
    i = -1;
    while (++i < a)
        ans[i] = 0;
    i = 0;
    while (++i <= b)
    {
        get_num_plus(num, tmp, i, 0);
        ans[num[0]- 1]++;
        ans[num[1]- 1]++;
    }
    i = -1;
    while (++i < a)
    {
        writing(ans[i]);
        write(1, "\n", 1);
    }
}

char *create_array(char *s, char *new_arr, char *t, int size)
{
    int i;
    int j;
    
    i = -1;
    while (s[++i])
        new_arr[i] = s[i];
    free(s);
    j = -1;
    while (++j < size)
        new_arr[i++] = t[j];   
    new_arr[i] = 0;
    return (new_arr);
}

char *get_data(char *s)
{
    int size;
    int sum_size;
    char t[1000];
    char *new_arr;
    
    sum_size = 0;
    while ((size = read(0, t, 1000)))
    {
        if (size == -1)
            return (NULL);
        sum_size += size;
        if (!(new_arr = (char*)malloc(sum_size + 1)))
            return (NULL);
        s = create_array(s, new_arr, t, size);
    }
    return (s);
}

int main(void){
    int num[2];
    char *s;
    
    s = malloc(1);
    s = get_data(s);
    
    get_nums(num, s, 0);
    get_ans(num[0],num[1], s);
    free(s);
    return (0);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll d1[4] = {1, -1, 0, 0};
ll d2[4] = {0, 0, 1, -1};

int main(){
    string c[4] = {"AC", "WA", "TLE", "RE"};
    map<string, ll> mp;
    ll n;
    cin >> n;
    rep(i, 0, n) {
        string s;
        cin >> s;
        mp[s]++;
    } 
    rep(i, 0, 4){
        cout << c[i] << " x " << mp[c[i]] << endl;
    }
    return 0;
}

Measured memory_bytes: 3632
N = int(input())
x = N
for i in range(N + 1):
	count = 0
	t = i
	while t > 0:
		count += int(t % 9)
		t = int(t / 9)
	t = N - i
	while t > 0 :
		count += int(t % 6)
		t = int(t / 6)
	if x > count:
		x = count
print(x)

Measured memory_bytes: 3060
#!/usr/bin/env python3
s = input().strip()

op = ('+', '-')

for bit in range(8):
    ops = [op[bool(bit & (0x01 << d))] for d in range(3)]
    eq = ''.join(sum(zip(s, ops + ['']), ()))
    if eval(eq) == 7:
        print(eq+'=7')
        exit()


Measured memory_bytes: 3060
s=list(input())

n=len(s)
n1=(n-1)//2
n3=(n+3)//2
s1=s[:n1]
s3=s[n3-1:]
#print(s3)
s3.reverse()

if s1!=s3:
    print("No")
else :
    m=len(s1)
    if m%2==1:
        m1=(m-1)//2
        m3=(m+3)//2
        s11=s1[:m1]
        s33=s1[m3-1:]
        s33.reverse()
        if s11==s33:
            print("Yes")
        else:
            print("No")
    else:
        m1=(m)//2
        m3=m1+1
        s11=s1[:m1]
        s33=s1[m3-1:]
        s33.reverse()
        if s11==s33:
            print("Yes")
        else:
            print("No")


Measured memory_bytes: 3064
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cstdlib>

#include <algorithm>
#include <numeric>
#include <limits>
#include <functional>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <queue>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N = 200010;

int n;
int a[N];

bool pred(int x) {
  map<int, int> cur;
  for (int i = 2; i <= n; ++i) {
    if (a[i] > a[i - 1])
      continue;
    int pos = a[i] - 1;
    cur.erase(cur.lower_bound(a[i]), cur.end());
    while (pos && cur[pos] == x - 1)
      cur.erase(pos--);
    if (cur[pos] == x - 1)
      return false;
    ++cur[pos];
  }
  return true;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif

  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &a[i]);
  bool flag = true;
  for (int i = 2; i <= n; ++i)
    flag &= a[i] > a[i - 1];
  if (flag) {
    puts("1");
    return 0;
  }
  int l = 2, r = n;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (pred(mid))
      r = mid;
    else
      l = mid + 1;
  }
  printf("%d\n", l);

#ifdef LBT
  LOG("Time: %dms\n", int((clock() - nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) {
  os << "{" <<p.first << ", " << p.second << "}";
  return os;
}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int a, b;
    cin >> a >> b;
    cout << (a - 1) * (b - 1) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=50050;

char s[maxn];
int main(){
    int n;
    scanf("%d", &n);

    if (n < 1200)  puts("ABC");
    else if (n < 2800)  puts("ARC");
    else  if (n < 666666)puts("AGC");
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<string>
using namespace std;

int main(){
	int a,b,c;
	int r = 0,l = 0;	
	while(scanf("%d,%d,%d",&a,&b,&c)==3){
		if(pow(c,2)==pow(a,2)+pow(b,2)){
			++r;
		}else if(a==b){
			l++;
		}
	}
	cout<<r<<endl<<l<<endl;
	return 0;
}

Measured memory_bytes: 1208
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;


public class A
{
	public static void Main()
	{
		string[] args = Console.ReadLine().Split(' ');
		int X = Int32.Parse(args[0]);
		int t = Int32.Parse(args[1]);
		Console.WriteLine(Math.Max(0, X - t));
	}
}





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

#define int long long

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  string s;
  cin >> s;
  
  bool flag = false;
  for ( int i = 0; i < (int)s.size()-1; i++ ) {
    if ( s[i] == s[i+1] ) flag = true;
  }

  if ( flag ) cout << "Bad" << endl;
  else cout << "Good" << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 100000000;
const ll half_inf = 0x3f3f3f3f;
const ll inf = 0x7fffffff;
const ll mod = 998244353;
const ll maxn = 2000005;
int m[50005]={0};
int main(){
	int n;
	scanf("%d",&n);
	for(int j1=2;j1<145;j1++){
		for(int j2=2;j2<145;j2++){
			for(int j3=2;j3<145;j3++){
				int a=j1+j3-j2,b=j1+j2-j3,c=j2+j3-j1;
				int k=j1*j1+j2*j2+j3*j3;
				if(k%2==0&&(a>0&&a%2==0)&&(b>0&&b%2==0)&&(c>0&&c%2==0)){
					m[k/2]++;
				}
			} 
		}
	}
		
		
		

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





Measured memory_bytes: 3932
N = int(input())
A = list(map(int, input().split()))
color = [False] * 8
over3200 = 0
for a in A:
    for i in range(8):
        if a < 400*(i+1):
            color[i] = True
            break
    else:
        over3200 += 1
if sum(color):
    print(sum(color), end=' ')
    print(sum(color) + over3200)
else:
    print(1, end=' ')
    print(over3200)


Measured memory_bytes: 3060
import java.io.*;

class Main{
	private static void sort(int[] a){
		for(int i = 0;i<a.length-1;i++){
			for(int j = a.length-1;j > i;j--){
				if(a[j] > a[j-1]){
					int t = a[j];
					a[j] = a[j-1];
					a[j-1] = t;
				}
			}
		}
	}
	private static void print_hill(int[] a){
		for(int i = 0;i<3;i++){
			System.out.println(a[i]);
		}
	}
		public static void main(String args[]) throws IOException{
			int hills[] = new int[10];
			InputStreamReader inp = new InputStreamReader(System.in);
			BufferedReader bre = new BufferedReader(inp);
			int n;
			for(int i = 0;i<10;i++){
				String num = bre.readLine();
				n = Integer.parseInt(num);
				hills[i] = n;
			}
			sort(hills);
			print_hill(hills);
	}
}

Measured memory_bytes: 9372
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <random>
#include <iomanip>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
typedef map<int, int> mii;
typedef set<int> si;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int
// #define endl '\n';
#define fi first
#define se second
#define NONVOID [[nodiscard]]
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
template<class T> inline void dump(T &v){irep(i, v){cout<<*i<<((i==--v.end())?'\n':' ');}}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("yes"):fin("no");}
inline void Yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;


int main() {
    
    int n;
    cin>>n;
    Yn(n/100==7||n/10%10==7||n%10==7);
}




Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    int k; cin >> k;
    if(k %2 == 0){
        int a = k/2;
        cout << a*a << endl; 
    }

    else{
        int a = k/2;
        cout << (a+1) * a << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <utility>
#include <vector>
#include <map>
#include <unordered_map>
#include <cstdlib>
#define div1 1000000007
const long long INF = 1LL << 60;
using namespace std;
using ll = long long;
// a>b -> a==b;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
// a<b -> a==b;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template <class T> void swap(T& a, T& b) { T t = std::move(a); a = std::move(b); b = std::move(t); }

int main(void)
{
    string s, s2, t;
    ll i, j, min=INF, judge, sum, ans=INF;

    cin >> s;

    s2 = s;

    if(s.size()>=2){
        judge = 1;
        for(i=1; i<s.size(); i++){
            if(s[i] != s[0]){
                judge = 0;
            }
        }
    }

    if(s.size()==1){
        cout << 0 << endl;
    }

    else if(judge == 1){ // 全て同じ
        cout << 0 << endl;
    }

    else{
        for(i=0; i<26; i++){ // アルファベット
            sum = 0;
            s = s2;
            judge = 0;
            while(judge == 0){
                sum++;
                t = "";
                judge = 1;

                for(j=0; j<s.size()-1; j++){
                    if(s[j]=='a'+i || s[j+1]=='a'+i){
                        t.push_back('a'+i);
                    }
                    else{
                        t.push_back(s[j]);
                        judge = 0;
                    }
                }

                s = t;

                if(judge==1){
                    break;
                }
            }

            chmin(ans, sum);
        }

        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())

signed main() {
    int n, k, x, y;
    cin >> n >> k >> x >> y;
    if(n > k) {
        cout << (n - k) * y + k * x << "\n";
    }else {
        cout << n * x << "\n";
    }

}

Measured memory_bytes: 256
def isPrime(x):
  """
  xが素数か否か判定する。

  Parameters
  ----------
  x: int
      自然数

  Returns
  -------
      True:素数
      False:素数ではない
  """
  if x<2:
    return False
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      return False
  return True


def sieve(x):
  """
  x以下の自然数が素数が否かを判定する。

  Parameters
  ----------
  x: int
      自然数

  Returns
  -------
  f:list
    True:素数
    False:素数以外
  """
  f=[True]*(x+1)
  f[0],f[1]=False,False

  for i in range(2,len(f)):
    if isPrime(i):
      for j in range(i*2,len(f),i):
        f[j]=False
  return f

n=int(input())
a=sieve(55555)
b=[]
for i,aa in enumerate(a):
  if aa==1:
    if i%5==1:
      b.append(i)
print(*b[:n])


Measured memory_bytes: 3444
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>
#include<math.h>

typedef int32_t i32;
typedef int64_t i64;

#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define ABS(a) ((a) > (0) ? (a) : -(a))

void run (void) {
  i64 n;
  scanf ("%" SCNi64, &n);
  i64 ans = 0;
  for (i64 i = 1;i <= n && (n - i) / i > i;++i) {
    if ((n - i) % i == 0) {
      ans += (n - i) / i;
    }
  }
  printf ("%" PRIi64 "\n", ans);
}

void test (void) {
  i64 n;
  scanf ("%" SCNi64, &n);
  for (i32 i = 1 ;i <= n; ++i) {
    printf ("%" PRIi32 " : ", i);
    for (i32 j = 1; j <= i; ++j) {
      if (i / j == i % j) {
	printf ("%" PRIi32 " ", j);
      }
    }
    puts ("");
  }
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i,x) for(int i=0;i<x;++i)
 
int main()
{
    string S; cin >> S;

    rep(i, S.size() - 1) {
        if (S[i] == S[i + 1]) {
            cout << i + 1 << ' ' << i + 2 << endl;
            return 0;
        }
    }

    rep(i, S.size() - 2) {
        if (S[i] == S[i + 2]) {
            cout << i + 1 << ' ' << i + 3 << endl;
            return 0;
        }
    }

    cout << "-1 -1\n";
}


Measured memory_bytes: 512
N = int(input())
S = input()

sleft = S[:N]
sright = S[2*N:N-1:-1]
ldict,rchoise = {},[]
count = 0
for i in range(2**N):
    red = bin(i)[2:].zfill(N)
    leftred, rightred, leftblue, rightblue = "","","",""
    for j in range(N):
        if red[j] == "1":
            leftred += sleft[j]
            rightred += sright[j]
        else:
            leftblue += sleft[j]
            rightblue += sright[j]
    if leftred + "-" + leftblue in ldict.keys():
        ldict[leftred + "-" + leftblue] += 1
    else:
        ldict[leftred + "-" + leftblue] = 1
    rchoise.append(rightred + "-" + rightblue)
    
for i in rchoise:
    count += ldict.get(i, 0)
print(count)

Measured memory_bytes: 56608
// #pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define N 1000000007
#define N2 998244353
#define Nmax 1000005
#define INF (ll)1e18
#define pll pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
#define vv vector
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(ll i=m;i<(n);i++)
#define repr(i,n) repr2(i,n,0)
#define repr2(i,m,n) for(ll i=m;i>=(n);i--)
#define get(n) ll (n); scanf("%lld",&(n));
#define get2(n,k) ll (n),(k); scanf("%lld%lld",&(n),&(k));
#define get3(n,m,k) ll (n),(m),(k); scanf("%lld%lld%lld",&(n),&(m),&(k));
#define gets(s) string (s); cin >> (s);
#define ALL(c) (c).begin(),(c).end()
#define fill_nums(A,n) vector<ll> A((n)); for(ll i=0;i<n;i++) scanf("%lld",&A[i]);
#define fill_edges(adj,m) for(ll i=0;i<m;i++) {ll a, b; scanf("%lld %lld",&a,&b); adj[a-1].pb(b-1); adj[b-1].pb(a-1);}
#define fill_direct(adj,m) for(ll i=0;i<m;i++) {ll a, b; scanf("%lld %lld",&a,&b); adj[a-1].pb(b-1);}
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); //cout.tie(0);
#define pi 3.1415926535897L
#define db long double  /* print with %Lf */
#define EPS 1e-9
#define flu fflush(stdout)
#define imp {cout<<"No\n"; return 0;}
#define yup {cout<<"Yes\n"; return 0;}
#define debug_vec(vec,n) {rep(idxi,n) cout<<vec[idxi]<<" "; cout<<"\n";}
#define debug_pvec(vec,n) {rep(idxi,n) cout<<vec[idxi].fi<<"-"<<vec[idxi].se<<"  "; cout<<"\n";}
#define debug_set(seta) {cout<<seta.size()<<"\n"; for(auto idxi:seta) cout<<idxi<<" "; cout<<"\n";}
#define debug_map(mappa) {cout<<mappa.size()<<"\n";for(auto idxi:mappa) cout<<idxi.fi<<"-"<<idxi.se<<"  "; cout<<"\n";}
#define debug_vecvec(vec,n) {rep(idxi,n) {for(auto idxi2:vec[idxi]) cout<<idxi2<<" "; cout<<"\n";}}
 
// LOOK AT THESE BEFORE SUBMISSION
// LOOK AT THESE BEFORE SUBMISSION
// ============================================================
// Nmax value and is index access offset taking it beyond Nmax.
// Precision error in case of real numbers.
// N vs N2 chosen correctly.
// Modulo applied everywhere.
// Flush in case of interactive.
// Don't erase value in multiset.
// Check for array indices out of bound (in pre or suff sums).
// Correct return value for functions.
// Confirm the letter case of yes and no.
// Dont paste code two times in the text file.
// ============================================================

int main() {
    get3(a,b,c);
    if((a==b) && a!=c) yup
    if((a==c) && a!=b) yup
    if((c==b) && a!=c) yup
    imp

    return 0;  
}   


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define N 3
#define N2 9
#define true 1
#define false 0

int P[N][N],lim;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

void solve(int,int);
int isTarget(void);
int bfs(int,int,int,int);

int main()  
{
  int i,j,px,py;
 for(i=0;i<N;i++){
   for(j=0;j<N;j++){
   scanf("%d",&P[i][j]);
   if(P[i][j]==0){
     px=i;
     py=j;  }}
 }
 solve(px,py);

 return 0;
}

void solve(int px,int py)
{
 for(lim=0;;lim++){
   if(bfs(0,99,px,py)){
     printf("%d\n",lim);
     return;}
                  }
}

int isTarget()
{
  int i,j,sum=0,x,s,t;
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
    if(P[i][j]==0)continue;
    x=P[i][j]-1;
    s=x/N-i;
    if(s<0)s=s*(-1);
    t=x%N-j;
    if(t<0)t=t*(-1);
    sum+=s+t;}}
  return sum;
}

int bfs(int depth,int prev,int px,int py)
{
  int h,r,tx,ty,p,q,z;
  h=isTarget();
  if(h==0)return true;
  if(depth+h>lim)return false;
 
    for(r=0;r<4;r++){
      if((r-prev)==2 && (r-prev)==-2)continue;  
      tx=px+dx[r];
      ty=py+dy[r];
      if(tx<0 || ty<0 || tx >=N || ty>=N)continue;
      
      z=P[tx][ty];
      P[tx][ty]=P[px][py];
      P[px][py]=z;
     
      if(bfs(depth+1,r,tx,ty))return true;
      z=P[tx][ty];
      P[tx][ty]=P[px][py];
      P[px][py]=z;
			 }
  return false;
}



  




Measured memory_bytes: 2084
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> h(n), f(n);
    for (int& hi : h) cin >> hi;
    for (int i = 1; i < n; ++i) {
        f[i] = numeric_limits<int>::max();
        for (int j = 1; j <= min(i, k); ++j)
            f[i] = min(f[i], f[i - j] + abs(h[i] - h[i - j]));
    }
    cout << f.back();
    return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    int n;
    cin >> n;
    string ans = "Yes";
    vector<int> a(n);
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int x = a[0];
    for (int i = 1; i < n; i++)
    {
        a[0] ^= a[i];
    }
    if(a[0]==0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 640
// Beginner 114 C.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
ll ans = 0, key;
void solve(ll sev, ll fif, ll th, ll pre)
{
    if (pre > key)
        return;
    else if (sev && fif && th)
        ans++;
    solve(sev + 1, fif, th, pre * 10 + 7);
    solve(sev, fif + 1, th, pre * 10 + 5);
    solve(sev, fif, th + 1, pre * 10 + 3);
}
int main()
{
    scanf("%lld", &key);
    solve(0, 0, 0, 0);
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int           long long
#define pb            push_back
#define ppb           pop_back
#define si            set <int>
#define endl          '\n'
#define fr            first
#define sc            second
#define mii           map<int ,int >
#define msi           map<string,int >
#define mis           map<int , string>
#define mci       	  map<char,int>  	
#define rep(i,a,b)    for(int  i=a;i<b;i++)
#define all(v)        v.begin(),v.end()
#define srt(v)        sort(all(v))
#define pii           pair<int ,int >
#define vi            vector<int >
#define vii           vector<pair<int , int >>
#define vs            vector<string>
#define sz(x)         (int )x.size()
#define M             1000000007
#define bs            binary_search
#define mp            make_pair
#define sp(n)         setprecision(n)
#define spl           " "
#define arr(a,n)      rep(i,0,n) cin>>a[i]
#define mod           998244353
#define MAXN   		  1000000
#define f(n) for(int i=0;i<n;i++)
using namespace std;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//#ifndef ONLINE_JUDGE
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//#endif
	int n;
	cin>>n;
	int a[n],b=0;
	rep(i,0,n)
	cin>>a[i];
	rep(i,1,n)
	{
		if(a[i]-a[i-1]<-1 || a[i]<b)
		{
			cout<<"No";
			return 0;
		}
		else if(a[i]-a[i-1]==-1)
		{
			b=a[i];
		}

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


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

const int MOD = 1000000007;

int main() {
    int N, K;
    cin >> N >> K;
    //long long sum = 0;
    vector<int> sum(N+1,0);

    // 計算例
    // for(int i=K; i<=N+1; ++i){
    //     long long max=0;
    //     long long min=0;
    //     for(int j=0; j<i; ++j){
    //         min += j;
    //     }
    //     for(int j=N; j> N-i; --j){
    //         max += j;
    //     }
    //     sum += (max - min+1);
    // }
    long long cumsum = 1;
    sum[K-1] = 1;
    for(int i=K; i<=N; ++i){
        cumsum +=i;
        sum[i] = (sum[i-1] + cumsum)%MOD;
    }

    long long res = sum[N] % MOD;
    cout << res << endl;
}

Measured memory_bytes: 3948
#include <stdio.h> 
 
 
 int main(){ 
     int i, j, k; 
     int n, x; 
     int count; 
 
 
     while(1){ 
         scanf("%d %d ", &n, &x); 
         if(n==0&&x==0)break; 
         count=0; 
         for(i=1;3*i+3<=x;i++){ 
             for(j=i+1;i+2*j+1<=x;j++){ 
                 for(k=n;k>j;k--){ 
                     if(x==i+j+k){ 
                         count++; 
                         break; 
                     }else if(x>=i+j+k){ 
                         break; 
                     } 
                 } 
             } 
         } 
         printf("%d\n", count); 
     } 
     return 0; 
 } 



Measured memory_bytes: 2128
#include <iostream>
#include<string.h>
#include<math.h>
using namespace std;
int main()
{  long long num=0;
   long long a,b,c,x,y;
   cin>>a>>b>>c>>x>>y;
   long long num1=max(x,y)*2*c;
   int sum3=min(x,y);
    num+=min(2*sum3*c,(a+b)*sum3);
    int sum4=max(x,y)-min(x,y);
    if(x>y) num+=min(a*sum4,2*c*sum4);
    else if(x<y) num+=min(b*sum4,2*c*sum4);
    cout<<min(num,num1)<<"\n";

}


Measured memory_bytes: 256
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 2 * 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

X, Y = map(int, input().split())
#(1, 2)の回数をn, (2, 1)の回数をmとする。
n = (-X + 2 * Y) / 3
m = (-Y + 2 * X) / 3
#いけない場合を除外
if n % 1 != 0:
  print(0)
  quit()
elif m % 1 != 0:
  print(0)
  quit()
#n + m C nで答え  
ans = cmb(int(n + m), int(n), p)
print(ans)




Measured memory_bytes: 132908
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
string s;
int main(){
	cin >> s;
	if(s[2] == s[3] && s[4] == s[5]) cout << "Yes" << endl;
	else cout << "No" << endl;
}

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

using namespace std;
using ll = long long;
inline int ri() { int n; cin >> n; return n;}

template<class M> class SegmentTree {
public:
	using T = typename M::value_type;
private:
	int m;
	int n;
	vector<T> data;
 
	T rec(int l, int r, int node, int node_l, int node_r) {
		if(node_r <= l || node_l >= r)return M::id;
		if(node_l >= l && node_r <= r)return data[node];
		int mid = (node_l + node_r) / 2;
		return M::op(
			rec(l, r, node * 2, node_l, mid),
			rec(l, r, node * 2 + 1, mid, node_r)
		);
	}
 
public:
	SegmentTree(const vector<T>& a) {
		m = a.size();
		for(n = 1; n < (int)a.size(); n <<= 1);
		data.resize(n<<1, M::id);
		for(int i = 0; i < (int)a.size(); i++)data[i + n] = a[i];
		for(int i = n - 1; i >= 1; i--) data[i] = M::op(data[i<<1], data[(i<<1) + 1]);
	}
 
	T get(int l, int r) {
		return rec(l, r, 1, 0, n);
	}
 
	void assign(int index, T val) {
		index += n;
		data[index] = val;
		while(index != 1){
			index >>= 1;
			data[index] = M::op(data[index<<1], data[(index<<1) + 1]);
		}
	}
 
	T operator[] (int i){
		return data[i + n];
	}
 
};
template<class T> class RMQ {
public:
	using value_type = T;
	static T op(T l, T r){return max(l, r);}
	static constexpr T id = -1e9;
};template <class T> constexpr T RMQ<T>::id;
const int MAX = 300010;




int main()
{
	int n, k; cin >> n >> k;
	vector<int> a(n);
	for(int i = 0; i < n; i++)cin >> a[i];
	SegmentTree<RMQ<int>> dp(vector<int>(MAX, 0));

	for(int i = 0; i < n; i++) {
		int l = max(0, a[i] - k);
		int r = min(MAX, a[i] + k + 1);
		int cur = dp.get(l, r) + 1;
		dp.assign(a[i], cur);
	}

	int ans = 0;
	for(int i = 0; i < MAX; i++) {
		ans = max(ans, dp[i]);
	}
	cout << ans << endl;

}

Measured memory_bytes: 9608
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T x,Args... args) {cout<<x<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;


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

string s, t;
cin >> s >> t;
sort(s.begin(), s.end());
sort(t.rbegin(), t.rend());

if(s < t)cout << "Yes" << endl;
else cout << "No"  << endl;


}




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

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    string ch;
    cin>>ch;
    int n;
    n=ch.size();
    int nb=0;
    for (int i=0;i<(n/2);i++)
        if (ch[i]!=ch[n-1-i])
            nb++;
    cout<<nb;

}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main(){
    int n=0,i,cnt[100]={0},j=0,max=0,longer=0,cou[100]={0};
    char str,save[100][100];
    while(1){
        scanf("%c",&str);
        if(str=='\n') break;
        if(str!=' '){
            if(isupper(str)) {
                str = tolower(str);
            }
            save[j][n]=str;
            n++;
            cou[j]++;
        }else{
            for(i=0;i<j;i++){
                if(!strcmp(save[i],save[j])){
                    cnt[i]++;
                }
            }
            j++;
            n = 0;
        }
    }
    for(i=0;i<=j;i++){
        if(cnt[max]<=cnt[i]) max=i;
    }
    for(i=1;i<=j+1;i++){
        if(cou[longer]<=cou[i]){
            longer=i;
        }
    }
    printf("%s %s\n",save[max],save[longer]);

    return 0;
}

Measured memory_bytes: 988
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define PI 3.1415926535897932384626433832795
int MOD=1e9+7;
int powmod(int a,int l, int md){int res=1;while(l){if(l&1)res=res*a%md;l/=2;a=a*a%md;}return res;}
typedef long long ll; typedef vector<ll> vi; typedef pair<ll, ll> ii; typedef vector<ii> vii;
#define pb push_back
int __set(int b, int i) {return b|(1<<i);} //set ith bit
int __unset(int b, int i) {return b&!(1<<i);}
int __check(int b, int i) {return b&(1<<i);} //returns 0 if ith bit is 0
int mul(int a, int b) {return ((a%MOD)*(b%MOD))%MOD;}
int add(int a, int b) {return (a+b)%MOD;}
int sub(int a, int b) {return (((a-b)%MOD)+MOD)%MOD;}
int __div(int a, int b) {return mul(a, powmod(b, MOD-2, MOD));} //if MOD is prime;
const ll inf = 0xFFFFFFFFFFFFFFFL; //very large number
priority_queue<int, vector<int>, greater<int> > pq; //for min priority_queue
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
clock_t time_p=clock();
void time()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
int getInvCount(vi& arr) 
{ 
	int n = arr.size();
    int inv_count = 0; 
    for (int i = 0; i < n - 1; i++) 
        for (int j = i + 1; j < n; j++) 
            if (arr[i] > arr[j]) 
                inv_count++; 
  
    return inv_count; 
} 
int32_t main(void)
{
	IOS;
	int mod=1000000007;
	int n, k; cin>>n>>k;
	vi a(n);
	for(int i = 0; i < n; i++) cin>>a[i];
	vi ki(n, 0); vi ni(n, 0);
	for(int i = 0; i < n; i++) {
		int ct=0;
		for(int j = 0; j < i; j++) {
			if(a[i] < a[j]) ct++;
		}
		ki[i]=ct;
		for(int j = i; j < n; j++) {
			if(a[i] < a[j]) ct++;
		}
		ni[i]=ct;
	}
	int sum1=0;
	// for(int i = 0; i < n; i++) cout<<ni[i]<<" ";
	// 	cout<<endl;
	// for(int j = 0; j < n; j++) cout<<ki[j]<<" ";
	// 	cout<<endl;
	for(int i = 0; i < n; i++)
 		sum1 = (sum1+ki[i])%mod;
 	sum1=(sum1*k)%mod;
 	int sum2=0;
 	for(int i = 0; i < n; i++)
 		sum2=(sum2+ni[i])%mod;
 	int prod=((k*(k-1))/2)%mod;
 	sum2 = (sum2*prod)%mod;
 	int ans=(sum1+sum2)%mod;
 	cout<<ans<<endl;
 	time();
	return 0;
}

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

typedef long long ll;

int main()
{
  int n;
  cin >> n;
  vector<ll> a(n);
  vector<ll> cnt(n + 1);
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
    cnt[a[i]]++;
  }
  
  ll ans = 0;
  for (ll i = 1; i < n + 1; i++)
  {
    ans += cnt[i] * (cnt[i] - 1) / 2;
  }
  for (ll i = 0; i < n; i++)
  {
    cout << ans - cnt[a[i]] + 1 << endl;
  }
}

Measured memory_bytes: 5760