akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int N,M,C;
    int s,c=0;
    cin >> N >> M >> C;
    vector<int> B(M);
    vector<vector<int>> A(N,vector<int>(M));
    for(int i = 0; i < M; i++)
    {
        cin >> B[i];
    }
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            cin >> A[i][j];
        }
    }
    for(int i = 0; i < N; i++)
    {
        s = 0;
        for(int j = 0; j < M; j++)
        {
            s += A[i][j] * B[j];
        }
        s += C;
        if (s > 0) {
            c++;
        }
    }
    cout << c << endl;
    return 0;
}

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

const int N = 200010;

int a[N];

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
        a[i] -= i;
    }
    std::sort(a + 1, a + n + 1);
    long long ans = 0;
    for (int i = 1; i <= n; ++ i){
        ans += std::abs(a[i] - a[n + 1 >> 1]);
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
    int n,k,r,s,p,i;
    cin>>n>>k>>r>>s>>p;
    ll sum=0;
    string t;
    cin>>t;
    vector<int> co(n);
    rep(i,n){
        co[i]=0;
    }
    for(i=0;i<n;i++){
        if(i-k<0){
            if(t[i]=='r'){
                sum+=p;
            }
            else if(t[i]=='s'){
                sum+=r;
            }
            else if(t[i]=='p'){
                sum+=s;
            }
        }
        if(i-k>=0){
            if(t[i]!=t[i-k]||co[i-k]==1){
                if(t[i]=='r'){
                    sum+=p;
                }
                else if(t[i]=='s'){
                    sum+=r;
                }
                else if(t[i]=='p'){
                   sum+=s;
                }
            }
            else{
                co[i]=1;
            }
            
        }

    }
    cout<<sum<<endl;
}

Measured memory_bytes: 896
#include<iostream>

#define R input[0][1]

using namespace std;

int input() {
	int input[51][2];
	cin >> input[0][0] >> input[0][1];								//まずnとr
	if (input[0][0] == 0 && input[0][1] == 0) {
		return 0;
	}
	for (char pos = 1; pos <= input[0][1]; pos++) {					//r回のシャッフルの仕方を入力
		cin >> input[pos][0] >> input[pos][1];
	}																//ここまで入力

	/*シャッフルもどし*/
	int whtop = 1;													//最後一番上にいるカードは、今何番目にいる？
	if (R==0)return input[0][0];									//一回もシャッフルしないならコレ
	while (input[0][1] != 0) {	
		if (whtop <= input[R][1]) whtop = whtop + input[R][0] - 1;
		else if ((input[R][0] + input[R][1] - 1) < whtop) whtop = whtop;
		else whtop = whtop - input[R][1];
		R--;
	}
	return input[0][0] - whtop + 1;

}


int main()
{
	while (1) {
		int check;
		check = input();
		if (check == 0)break;
		else cout << check << endl;
	}
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#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 fs first
#define sc second
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main(){
  string a,b;
  cin>>a>>b;
  if(a.size()>=b.size()&&a>b)
  cout<<"GREATER"<<endl;
  else if(a==b) cout<<"EQUAL"<<endl;
  else cout<<"LESS"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <stdio.h>
#include <math.h>


using namespace std;

typedef long long ll;

typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<ll> vll;

typedef pair<int, int> P;

typedef queue<int> qi;
typedef queue<string> qs;


#define rep(i, n) for(int i=0; i<(n); ++i)
#define repp(i, a, b) for(int i = (a); i <= (b); i++)
#define Rep(i, n) for(int i=n; i >= 0; i--)

#define all(v) v.begin(), v.end()
//sort( all(v) )　などと使える

/*
int main() {
	ll n; cin >> n;

	string c;

	
	while(n){
		ll r = n % 26;
		string s;
		s = (char)((int)r + 96);

		s += c;

		c = s;

		//cout << r + 96 << endl;

		n /= 26;
	}

	cout << c << endl;
	return 0;
}
*/



ll ll_max(int a, ll b) {
	ll A = (ll)a;
	if (A > b) return A;
	else return b;
}

int main() {
	ll n; cin >> n;
	string ans;

	while (n) {
		n--;
		ans = (char)('a' + n % 26) + ans;
		n /= 26;
	}

	cout << ans << endl;
}


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

int sq(int x) {
    return x * x;
}

int main() {
    int h, w;
    while (cin >> h >> w, h | w) {
        int d = h * h + w * w,
            ans_d = 100000000,
            ans_h = 1000, ans_w;
        for (int w_i = 1; w_i <= 150; w_i++) {
            for (int h_i = 1; h_i <= 150; h_i++) {
                if (w_i <= h_i) continue;
                if (w_i == w && h_i == h) continue;
                int d2 = sq(w_i) + sq(h_i);
                if (d2 < d) continue;

                if (d2 == d && h_i <= h) {
                    continue;
                }

                if (ans_d > d2) {
                    ans_h = h_i;
                    ans_w = w_i;

                    ans_d = sq(ans_h) + sq(ans_w);
                } else if (ans_d == d2 && ans_h > h_i) {
                    ans_h = h_i;
                    ans_w = w_i;

                    ans_d = sq(ans_h) + sq(ans_w);
                }
            }
        }
        cout << ans_h << " " << ans_w << endl;
    }
    return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        var nk = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var s = Console.ReadLine();

        var pre = s[0];
        var count = Enumerable.Repeat(0, nk[0] - 1).ToArray();
        var index = 0;
        foreach (var c in s.ToCharArray().Skip(1))
        {
            if (pre == c)
            {
                count[index] += 1;
            }
            else
            {
                ++index;
            }

            pre = c;
        }

        var answer = count.Sum();

        foreach (var x in count.OrderBy(x => x).Take(nk[1]))
        {
            answer += 2;
        }

        if (answer >= nk[0]) answer = nk[0] - 1;

        Console.WriteLine(answer);
    }
}

Measured memory_bytes: 16608
def calc_matrix(A, B, size):
    n, m, l = size
    # print(n, m, l)

    results = []
    for i in range(n):
        row_data = []
        for j in range(l):
            products = []
            for k in range(m):
                products.append(A[i][k] * B[k][j])
            # print('C[{0}][{1}] = {2}'.format(i, j, sum(products)))
            row_data.append(sum(products))
        results.append(row_data)
    return results


if __name__ == '__main__':
    # ??????????????\???
    A = []
    B = []
    # A.append([1, 2])
    # A.append([0, 3])
    # A.append([4, 5])
    # B.append([1, 2, 1])
    # B.append([0, 3, 2])
    n, m, l = [int(x) for x in input().split(' ')]
    for i in range(n):
        A.append([int(x) for x in input().split(' ')])
    for i in range(m):
        B.append([int(x) for x in input().split(' ')])

    # ???????????????
    results = calc_matrix(A, B, (n, m, l))

    # ???????????????
    for row in results:
        print(' '.join(map(str, row)))

Measured memory_bytes: 8908
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,d,n,cnt;
  int arr[1000001];
  const int N = 1000000; //N までの素数を表示
  for(int i = 2; i < N; i++){
    arr[i] = 1;
  }
  for(int i = 2; i < sqrt(N); i++){
    if(arr[i]){
      for(int j = 0; i * (j + 2) < N; j++){
	arr[i *(j + 2)] = 0;
      }
    }
  }
  while(cin>>a>>d>>n&&(a||d||n)){
    cnt = 0;
    for(int i = a; i < N; i+=d){
      
      if(arr[i]){
	cnt++;
	if(cnt==n){
	  printf("%d\n",i);
	  break;
	}
      }
    }
  }
}

Measured memory_bytes: 5048
#include <iostream>
// #include <vector> 
#include <algorithm>
#include <queue>
#include <cstdio> 
using namespace std;
static const int MAX = 10000;
static const int INFTY = (1<<20);
int d[MAX],color[MAX];
int n;
vector<pair<int, int> > adj[MAX];

void dijkstra()
{
    priority_queue<pair<int, int> > PQ;
    for (int i = 0; i < n; i++)
    {
        d[i] = INFTY;
        color[i] = 0;
    } 
    d[0] = 0;
    PQ.push(make_pair(0,0));
    color[0] = 1;
    while (!PQ.empty())
    { 
        pair<int, int> f = PQ.top(); PQ.pop();
        int u = f.second;
        // cout<<u<<" "<<color[u]<<endl;
        color[u] = 2;
        
        //if (d[u] < f.first * (-1)) continue;
        
        for (int j = 0; j < adj[u].size(); j++)
        {
            int v = adj[u][j].first;
            //if (color[v] == 2) continue;
            if (color[v] != 2 && d[v] > d[u] + adj[u][j].second)
            { 
                d[v] = d[u] + adj[u][j].second;
                PQ.push(make_pair(d[v] * (-1), v));
                color[v] = 1;
            } 
        } 
    } 

    return;
}


int main()
{
    //freopen("in3.txt","r",stdin);
    int u,k,v,c;
    cin>>n;
    for (int i = 0; i < n; i++)
    {
        cin>>u>>k;
        for (int j = 0; j < k; j++)
        {
            cin>>v>>c;
            adj[u].push_back(make_pair(v,c));
        } 
    } 
    dijkstra();
    for (int i = 0; i < n; i++)
    {
        cout<<i<<" "<<d[i]<<endl; 
    } 
    return 0;
}

Measured memory_bytes: 8100
#include <iostream>
#include <map>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string>
#include <stack>
#include <set>
#include <deque>
#define mp make_pair
using namespace std;
int n,a,b,x[50],y[50],c[50],mini=100000000;
int used[505][505];
bool u[50];
void dfs(int cost,int g1,int g2){
	if (g1*b==g2*a && g1!=0 && g2!=0) mini=min(mini,cost);
	if (used[g1][g2]<=cost){
		return;
	}
	used[g1][g2]=cost;
	for (int i=0;i<n;i++){
		if (!u[i]){
			u[i]=true;
			dfs(cost+c[i],g1+x[i],g2+y[i]);
			u[i]=false;
		}
	}
}
int main(){
	cin>>n>>a>>b;
	for (int i=0;i<n;i++){
		cin>>x[i]>>y[i]>>c[i];
	}
	for (int i=0;i<505;i++) for (int j=0;j<505;j++) used[i][j]=1000000;
	dfs(0,0,0);
	if (mini!=100000000) cout<<mini; else cout<<-1;
	return 0;
}

Measured memory_bytes: 1280
#include <bits//stdc++.h>
using namespace std;
int main(void){
    string s,w,z;
    cin >> s >> w;
    for(int i=0;i<s.size();i++){
        cout << s[i] ;
        if(i<w.size()){
            cout << w[i] ;
        }
    }
    cout << endl;
    return 0;
}


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

using namespace std;

const int mod = 1e9+7;
#define ll long long int
const double epsilon = 1e-7;

ll ma(ll x, ll y){
    if(x>y)return x;
    return y;
}
int a[200000];
int main(void){
    int n;
    scanf("%d", &n);
    for(int i = 0;i < n;i++)scanf("%d", &a[i]);
    ll sum = 0;
    ll xs = 0;
    ll ans = 0;
    int count = 0;
    for(int i = 0;i < n;i++){
        while(true){
            if(i+count > n-1){
                ans += (ll)count * (count + 1) / 2;
                goto a;
            }
            sum += a[i+count];
            xs ^= a[i+count];
            //printf("%lld, %lld\n", sum, xs);
            if(sum == xs)count++;
            else{
                ans += count;
                sum -= a[i];
                xs ^= a[i];
                if(count > 0){
                    sum -= a[i+count];
                    xs ^= a[i+count];
                    count--;
                }
                break;
            }
        }
    }
    a:
    printf("%lld\n", ans);
    return 0;
}


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

int main(){
    int n, t;
    cin >> n >> t;
    vector<pair<int, int>> dish(n);
    for (int i = 0; i < n; i++) cin >> dish[i].first >> dish[i].second;
    //dp[i][j][k] -> i個目まで見た時、コストj以下で達成できる価値の最大値(おまけあり、なしをkで表す)
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(t, vector<int>(2, 0)));
    for (int i = 0; i < n; i++){
        for (int k = 0; k < 2; k++){
            if (dish[i].first < t) dp[i + 1][dish[i].first][k] = max(dp[i + 1][dish[i].first][k], dish[i].second);
            for (int j = 0; j < t; j++){
                dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
                if (j + dish[i].first < t) dp[i + 1][j + dish[i].first][k] = max(dp[i + 1][j + dish[i].first][k], dp[i][j][k] + dish[i].second);
                if (j != t - 1) dp[i + 1][j + 1][k] = max(dp[i + 1][j][k], dp[i + 1][j + 1][k]);
            }
        }
        //おまけの辺は、i - 1個まで見た時の値に、おまけするという遷移でいける
        for (int j = 0; j < t; j++) dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j][0] + dish[i].second);
    }
    cout << max(dp[n][t - 1][0], dp[n][t - 1][1]) << endl;
}

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
#define int ll

const ll MOD = 1000000007;
const ll INF_LL = (ll)1000000007 * 1000000007;
const int INF_INT = (int)1000000007;
const double PI = 3.14159265358979323846;

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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define irep(itr, st) for (auto itr = (st).begin(); itr != (st).end(); ++itr)
#define irrep(itr, st) for (auto itr = (st).rbegin(); itr != (st).rend(); ++itr)

#define m0(x) memset((x), 0, sizeof((x)))
#define m1(x) memset((x), -1, sizeof((x)))

// xにはvectorなどのコンテナ
#define ALL(x) (x).begin(), (x).end()  // sortなどの引数を省略したい
#define RALL(x) (x).rbegin(), (x).rend()  // sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())     // sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))  //最大値を求める
#define MIN(x) *min_element(ALL(x))  //最小値を求める
#define all(x) (x).begin(), (x).end()

//略記
#define pb emplace_back  // vectorヘの挿入
#define mp make_pair     // pairのコンストラクタ
#define F first          // pairの一つ目の要素
#define S second         // pairの二つ目の要素

#define BITCOUNT __builtin_popcount
#define BITCOUNT_LL(x) __builtin_popcountll(x)

#define perm(c)             \
  sort(all(c));             \
  for (bool c##p = 1; c##p; \
       c##p = next_permutation(all(c)))  //順列 123 132 213 231 312 321

#define BIT(n) (1LL << (n))

#ifdef DEBUG
#define PRINT(A) std::cout << (#A) << ": " << (A) << std::endl;
#else
#define PRINT(A)
#endif

//入力高速化
struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

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

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

signed main() {
  int A;
  double B;
  cin >> A;
  cin >> B;
  B*= 100;
  B+= 0.1;
  int ans = A * ((int)B) / 100;

  cout << ans << endl;
}

Measured memory_bytes: 3752
//  SMOKE SHISHA PLAY FIFA  // 
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pll pair<ll,ll>
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define mod 1000000007
#define lp(start,end) for(ll i=start;i<=end;i++) 
#define deb1(a) cout<<#a<<" = "<<(a)<<endl;
#define deb2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;
#define deb3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;


ll modu(ll a, ll b)
{
	ll ans =1;
	while(b>0)
	{
		if(b&1)
		ans = (ans*a)%mod;
		b/=2;
		a = (a*a)%mod;
	}
	return ans;
}

int main()
{
	fastio
	ll x;
	cin >> x;
	if(x<600)
		cout << "8" << endl;
	else if(x<800)
		cout << "7" << endl;
	else if(x<1000)
		cout << "6" << endl;
	else if(x<1200)
		cout << "5" << endl;
	else if(x<1400)
		cout << "4" << endl;
	else if(x<1600)
		cout << "3" << endl;
	else if(x<1800)
		cout << "2" << endl;
	else if(x<2000)
		cout << "1" << endl;
	return 0;	
}


Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <utility>
#include <vector>
#include <tuple>
#include <numeric>
using namespace std;

int gcd(int a, int b){
	if(a%b==0){
		return b;
	}else{
		return(gcd(b, a%b));
	}
}

int lcm(int a, int b){
	return(a*b/gcd(a, b));
}

int main(int argc, char* argv[]){
	int n;
	scanf("%d", &n);

	int LCM = lcm(360, n);

	printf("%d\n", LCM/n);


	return 0;
}


Measured memory_bytes: 3728
#include <iostream>
#include <string>
#include <map>
#include <algorithm>

using namespace std;
using ll = long long;
using ld = long double;

int main() {
  ll N;
  cin >> N;
  string str;
  map<string,int> m;
  for (int i = 0; i != N; ++i) {
    cin >> str;
    m[str] += 1;
  }


  const auto maxcnt =
      max_element(m.begin(),m.end(),
                  [](auto &p1, auto &p2) {
                    return p1.second < p2.second;
                  })->second;

  for (auto it = m.begin(); it != m.end(); ++it) {
    if (it->second == maxcnt) {
      cout << it->first << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 27264
s = input()

ans = 0
cnt = 0  # グーを出した回数-パーを出した回数; cntが負になったらダメ

for i in range(len(s)):
    if cnt == 0:
        AtCoDeer = 'g'
        cnt += 1
    else:
        AtCoDeer = 'p'
        cnt -= 1

    if AtCoDeer == 'p' and s[i] == 'g':
        ans += 1
    elif AtCoDeer == 'g' and s[i] == 'p':
        ans -= 1

print(ans)


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

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

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll INF = 1LL<<60;

int main() {
  int K;
  cin>>K;
  vector<ll> v(K);
  for(int i = 0; i < K; i++) cin>>v[i];
  reverse(v.begin(),v.end());
  bool can = true;
  ll xM=2LL,xm=2LL;
  for(int i = 0; i < K; i++){
    if(xM/v[i]-(xm-1LL)/v[i]==0LL){
      can=false;
      break;
    }
    xM=(xM/v[i])*v[i]+v[i]-1;
    xm=((xm-1LL)/v[i]+1LL)*v[i];
  }
  if(can) cout<<xm<<" "<<xM<<endl;
  if(!can) cout<<-1<<endl;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		int n1 = n%10;
		int n2 = (n/10)%10;
		int n3 = (n/100)%10;
		int n4 = (n/1000);
		if(n1==n2 && n2==n3){
			System.out.println("Yes");
			return;
		}
		else if(n2==n3 && n3==n4){
			System.out.println("Yes");
			return;
		}
		else{
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 23764
from scipy.misc import comb

N, K = map(int, input().split())

mod = 10**9 + 7

for i in range(1, K+1):
    blue = comb(K-1, i-1, exact=True)
    red_count = N - K
    red = comb(red_count+1, i, exact=True)
    print(blue * red % mod)


Measured memory_bytes: 14108
#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;
const ll MOD=998244353;
int main()
{
	int n, m;
    cin>>n>>m;
    cout<<(n+m)*(n+m-1)/2-n*m<<endl;
	return 0;
}


Measured memory_bytes: 256
mod = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == '?':
        for j in range(13):
            for k in range(10):
                jj = (10 * j + k) % 13
                dp[i + 1][jj] = (dp[i + 1][jj] + dp[i][j]) % mod
    else:
        k = int(s[i])
        for j in range(13):
            jj = (10 * j + k) % 13
            dp[i + 1][jj] = (dp[i + 1][jj] + dp[i][j]) % mod
print(dp[n][5])

Measured memory_bytes: 95804
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)
#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



#ifdef __APPLE__
const int N = 1e2+50;
#else
const int N = 1e6+50;
#endif

ll n,x;
ll solve(ll a, ll b) {
	if (!b) return -a;
	return a/b*2*b+solve(b,a%b);
}
int main() {
	cin>>n>>x;
	cout<<solve(n-x,x)+n<<endl;
}



Measured memory_bytes: 256
import math
n = int(input())
s = int(input())

result = -1
if n == s:
  result = n + 1
elif s > n:
  pass
else:
  temp_sqrt_n = math.floor(math.sqrt(n))
  for b in range(2, temp_sqrt_n + 1):
    temp_n = n
    temp_b = 0
    while temp_n >= b:
      temp_b += temp_n % b
      temp_n = temp_n // b
    if temp_b + temp_n == s:
      result = b
      break
  if result == -1:
    temp_sqrt_n = math.floor(math.sqrt(n - 1))
    for quot in range(temp_sqrt_n, 0, -1):
      if n - s % quot != 0:
        b = (n - s) // quot + 1
        if quot + n % b == s:
          result = b
          break
print(result)

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

int main(){
	string str;
	string word[1000];
	int rate[1000], kind = 0;
	int M_leng = 0, mode;
	string res_mod, res_len;
	bool new_word;
	
	for(int i = 0; i < 1000; i++) rate[i] = 0;
	while((cin >> str)){
		new_word = true;
		for(int i = 0; i < kind; i++){
			if(str == word[i]){
				new_word = false;
				rate[i]++;
				break;
			}
		}
		
		if(new_word){
			word[kind] = str;
			rate[kind]++;
			kind++;
		}
	}
	
	mode = 0;
	for(int i = 0; i < kind; i++){
		if(mode < rate[i]){
			res_mod = word[i];
			mode = rate[i];
		}
		if(M_leng < word[i].size()){
			res_len = word[i];
			M_leng = word[i].size();
		}
	}
	
	cout << res_mod << " " << res_len << endl;
	
	return 0;
}

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

using namespace std;

#define int long long

const int N = 2e5+7, mod = 1e9+7;

int f[N], inv[N];

int binpow(int a,int b){
	int res = 1;
	while(b>0){
		if(b&1) (res*=a)%=mod, --b;
		(a*=a)%=mod, b>>=1;
	}
	return res;
}

int inverse(int x){
	return binpow(x, mod-2);
}

void preset(){
	f[0] = 1, inv[0] = 1;
	for(int i=1;i<N;++i) f[i] = (f[i-1]*i)%mod, inv[i] = inverse(f[i]);
}

int C(int k,int n){
	return (((f[n]*inv[k])%mod)*inv[n-k])%mod;
}

int h,w,a,b;

signed main(){
	preset();
	cin >> h >> w >> a >> b;
	int ans = 0;
	for(int i=1;i<=h-a;++i){
		// (1,1) -> (i,b) -> (i,b+1) -> (h,w) 
		(ans+=C(i-1,i-1+b-1)*C(h-i,h-i+w-b-1))%=mod;
	}
	cout << ans;
}

Measured memory_bytes: 6760
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product
from collections import Counter

n, a, b, c, *l = map(int, read().split())
ans = float('inf')
for bit in product([0, 1, 2, 3], repeat=n):
    if 0 not in bit or 1 not in bit or 2 not in bit:
        continue
    counter = Counter()
    memo = 0
    for ll, num in zip(l, bit):
        if num == 3:
            continue
        if counter[num] != 0:
            memo += 10
        counter[num] += ll
    ans = min(ans, abs(counter[0] - a) + abs(counter[1] - b) + abs(counter[2] - c) + memo)
print(ans)


Measured memory_bytes: 3316
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r + 1):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    return i


def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)


def makedic(A, n):
    d = {}
    for i in range(n):
        key = A[i][1]
        value = A[i][0]
        if key in d:
            d[key] += value
        else:
            d[key] = value
    return d

def main():
    N = int(input())
    A = []
    for i in range(N):
        a, v = input().split()
        v = int(v)
        A.append((a, v))

    sd = makedic(A, N)
    quicksort(A, 0, N - 1)
    ed = makedic(A, N)

    print('Stable' if sd == ed else 'Not stable')

    for l in A:
        print(l[0], l[1])

if __name__ == '__main__':
    main()






Measured memory_bytes: 22148
#include <bits/stdc++.h>
#include<algorithm>
#define int long long
using namespace std;
typedef pair<int,int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1000000000000

int MOD=1000000007;
int modpow(int a,int x){
  if(a<0)a+=MOD;
  int ans=1;
  while(x>0){
    if(x&1) ans=ans*a%MOD;
      a=a*a%MOD;
      x>>=1;
  }
  return ans;
}

int gyaku(int n){
    return modpow(n,MOD-2);
}
////////////////////////////////////////////////////////////

signed main() {
  int n;
  cin>>n;
  map<int,int>sosuu;
  for(int i=2;i<=(int)pow(n,0.5)+1;i++){
    int count=0;
    while(n%i==0){
      n=n/i;
      count++;
    }
    if(count)sosuu[i]=count;
  }
  if(n!=1)sosuu[n]++;
  int ans=0;
  for(auto [a,b]:sosuu){
    for(int k=1;k<=48;k++)if(b>=k*(k+1)/2&&b<=(k+2)*(k+1)/2-1)ans+=k;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 4052
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

const int MAXN = 1e5 + 10;

int n, q, a[MAXN], b[MAXN], cnt[MAXN];

int main(){
	scanf("%d %d", &n, &q);
	memset(a, -1, sizeof(a));
	memset(b, -1, sizeof(b));
	a[0] = 0;
	int pos = 0;
	fill(cnt, cnt + n, 1);
	for (int i = 1; i <= q; i++){
		int x, y;	scanf("%d %d", &x, &y), x--, y--;
	
		cnt[x]--;
		cnt[y]++;
	
		if (a[x] > b[x])	a[y] = i;
		if (cnt[x] == 0)	b[x] = i;
	}

	int ans = 0;
	for (int i = 0; i < n; i++)
		if (a[i] > b[i])	ans++;
	printf("%d\n", ans);
	return 0;
}


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

const int sz = 1 << 18;

long long data[sz << 1], lazy[sz << 1];

void eval(int k) {
    data[k] += lazy[k];
    if(k < sz) {
        lazy[k << 1] += lazy[k];
        lazy[k << 1 | 1] += lazy[k];
    }
    lazy[k] = 0;
}
void add(int a, int b, long long x, int k = 1, int l = 0, int r = sz) {
    eval(k);
    if(b <= l || r <= a) return;
    if(a <= l && r <= b) {
        lazy[k] += x;
        eval(k);
    } else {
        add(a, b, x, k << 1, l, l + r >> 1);
        add(a, b, x, k << 1 | 1, l + r >> 1, r);
        data[k] = max(data[k << 1], data[k << 1 | 1]);
    }
}
long long getmax(int a, int b, int k = 1, int l = 0, int r = sz) {
    if(b <= l || r <= a) return -1LL << 60;
    eval(k);
    if(a <= l && r <= b) return data[k];
    long long vl = getmax(a, b, k << 1, l, l + r >> 1);
    long long vr = getmax(a, b, k << 1 | 1, l + r >> 1, r);
    return max(vl, vr);
}

int N, M;

vector<pair<int, int>> P[200009];

int main() {
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int l, r, a;
        cin >> l >> r >> a;
        P[r].push_back(make_pair(l, a));
    }

    for(int i = 1; i <= N; i++) {
        add(i, i + 1, getmax(0, i));
        for(auto p : P[i]) {
            int l = p.first;
            int a = p.second;
            add(l, i + 1, a);
        }
    }

    cout << getmax(0, N + 1) << endl;

    return 0;
}

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n,k; cin>>n>>k;
	if (n%k) cout<<"1"<<endl;
	else cout<<"0"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 100000
#define Q 50000

int main(){
  int S[N], T[Q], C = 0;
  int left, right, mid, key;
  int n, q, i;

  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%d", &S[i]);
  }

  scanf("%d", &q);
  for(i = 0; i < q; i++){
    scanf("%d", &T[i]);
  }

  for(i = 0; i < q; i++){
    key = T[i];
    left = 0;
    right = n;

    while(left < right){
      mid = (left + right) / 2;
      if(S[mid] == key){
        C++;
        break;
      }
      else if (key < S[mid]){
        right = mid;
      }
      else left = mid + 1;
    }
  }

  printf("%d\n", C);

  return 0;
}

Measured memory_bytes: 1184
#include <cstdio>
#include <cstring>

char str[2000005];
int main() {
    scanf("%s", str);
    int len = strlen(str), sum = 0;
    for (int i = 0; i < len; i++) {
        sum += str[i] - '0';
    }
    if (sum % 9 == 0) printf("Yes");
    else printf("No");
    return 0;
}

Measured memory_bytes: 3380
#include<stdio.h>
main()
{
    int n,i,j,k,c=0,d=0,e=0;
    scanf("%d",&n);
    if(n<10){
        for(i=1;i<=n;i++){
            c++;
            if(i==n){
                printf("%d\n",c);
            }
        }
    }
    else if(n>=10 && n<=99){
        printf("9\n");
    }
    else if(n>=100 && n<=999){
        for(j=100;j<=n;j++){
                d++;
                if(j==n){
                   break;
                }
           }
           printf("%d\n",(9+d));
      }
      else if(n>=1000 && n<=9999){
              printf("909\n");
      }
      else if(n>=10000 && n<=99999){
             for(k=10000;k<=n;k++){
                e++;
                if(k==n){
                   break;
                }
             }
             printf("%d\n",(909+e));
      }
      else if(n==100000){
        printf("90909\n");
      }
      return 0;
}


Measured memory_bytes: 1728
#include <bits/stdc++.h>
using namespace std;
#define elif else if
typedef long long ll;
typedef unsigned long long ull;
#define DEBUG(x) cout << (x) << endl

ll n,k;
int arr[200005];
int step[200005]={0};

int main()
{
    scanf("%lld %lld", &n, &k);
    for (int i = 1; i <= n;i++)
    {
        scanf("%d", arr + i);
    }
    int pos = 1;
    int cur = 2;
    step[1] = 1;
    while(k)
    {
        pos = arr[pos];
        k -= 1;
        if(step[pos]!=0)
        {
            // printf("%d %d\n", pos, cur - step[pos]);
            k %= cur - step[pos];
            while(k)
            {
                pos = arr[pos];
                k -= 1;
            }
        }
        step[pos] = cur++;
    }
    printf("%d\n", pos);
    return 0;
}

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

//#define int long long
typedef long long ll;
//const int INF = 2e9;
//const ll INF = 9e18;

const int mod = 1000000007;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    string S1, S2;
    cin >> S1;
    cin >> S2;
    mint ans = 1;
    int prev;
    int start = 0;
    if (S1[0]==S2[0]) {
        prev = 0;
        ans *= 3;
        start = 1;
    } else {
        prev = 1;
        ans *= 6;
        start = 2;
    }
    for (int i=start;i<N;i++){
         if (S1[i] == S2[i]){
             if (prev == 0){
                prev = 0;
                ans *= 2;
             } else {
                prev = 0;
                ans *= 1;
             }
         } else {
             if (prev == 0){
                prev = 1;
                ans *= 2;
                i++;
             } else {
                prev = 1;
                ans *= 3;
                i++;
             }
         }
    }
    cout << ans << "\n";
}

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

#define int long long

#define MOD 1000000007

int n, a, b, c, d;

int kai[1010];
int memo[1010][1010];

void init(){
    kai[0] = 1;
    for(int i = 1;i < 1010;i++){
        kai[i] = (kai[i-1] * i) % MOD;
    }
}

int pow_mod(int n, int m){
    int ans = 1;

    while(m > 0){
        if(m & 1) ans = (ans * n) % MOD;
        n = (n * n) % MOD;
        m >>= 1;
    }

    return ans;
}


int combi(int n, int r){
    return ((kai[n] * pow_mod(kai[r], MOD-2) % MOD) * pow_mod(kai[n-r], MOD-2)) % MOD;
}

int memo2[1010][1010] = {};

int dp(int i, int j){
    if(j == 0) return 1;
    if(i > b)  return 0;
    if(memo[i][j] != -1) return memo[i][j];

    int ans = dp(i+1, j);

    int tmp = 1;
    int tt = j;
    int tt2 = 1;
    int cnt = 1;

    for(int num = 1;num < c;num++){
        tt -= i;
        if(tt < 0) return memo[i][j] = ans;
        tt2 = (tt2 * cnt) % MOD;
        cnt++;
        tmp = (tmp * combi(tt+i, i)) % MOD;
    }

    for(int num = c;num <= d;num++){
        tt -= i;
        tt2 = (tt2 * cnt) % MOD;
        cnt++;
        if(tt < 0) return memo[i][j] = ans;
        tmp = (tmp * combi(tt+i, i)) % MOD;
        ans = (ans + (dp(i+1, j-num*i) * (tmp*pow_mod(tt2, MOD-2) % MOD)) % MOD) % MOD;
    }

    return memo[i][j] = ans;
}

signed main(){

    init();

    cin >> n >> a >> b >> c >> d;

    memset(memo, -1, sizeof(memo));

    cout << dp(a, n) << endl;

    return 0;
}



Measured memory_bytes: 10112
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
using namespace std;
int main()
{
  int a,b,k;
  cin>>a>>b>>k;

  if(k%2==0)
  {
  int cnt=k/2;
  while(cnt>0)
  {
    if(a%2==1) a-=1;
    a/=2;
    b=b+a;

    if(b%2==1) b-=1;
    b/=2;
    a=a+b;

    cnt--;
 }
 }

  else
  {
    int cnt=(k-1)/2;
    while(cnt>0)
    {
    if(a%2==1) a-=1;
    a/=2;
    b=b+a;

    if(b%2==1) b-=1;
    b/=2;
    a=a+b;

    cnt--;
   }

  if(a%2==1) a-=1;
  a/=2;
  b=b+a;
  }

  cout<<a<<' '<<b<<endl;
}

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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//print
#define pv(val) cerr << #val << '=' << (val) << endl

const int INF = 1e9;
const int MAX = 100 * 100 + 5;

int main(void){

	int N; cin >> N;
	vector<int> s(N);

	REP(i,N) cin >> s[i];

	vector<bool> dp(MAX, false);
	dp[0] = true;

	REP(i,N){
		for(int j=MAX-1;j >= 0;j--){
			int tmp = j + s[i];
			if(dp[j] and tmp){
				dp[tmp] = true;
			}
		}
	}
	int ans = 0;
	REP(i,MAX){
		if(dp[i] and i % 10 != 0) ans = max(ans, i);
	}

	cout << ans << endl;



	return 0;

}


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

class Program
{
    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
        //MyDebugger.Test(process, "../TextFile2.txt");
        //MyDebugger.MakeTestCase("../TextFile2.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var h = long.Parse(input.ReadLine());

        long x = 1;
        long n = 1;
        while (true) {
            if (x >= h) break;
            
            x = x * 2 + 1;
            n = n + n * 2 - 1;
        }
        return x;
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N=1e5+5;

int32_t main()
{
	IOS;
	string s;
	cin>>s;
	int ans=s.size();
	stack<char> st;
	for(auto &it:s)
	{
		if(it=='S')
			st.push(it);
		else
		{
			if(st.size())
			{
				st.pop();
				ans-=2;
			}
		}
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 720
K = int(input())

def cal():
    count = 9
    d = [[1,2,3,4,5,6,7,8,9]]
    for i in range(10**9):
        d_ = []
        for j in range(len(d[i])):
            a = str(d[i][j])
            if a[-1]=="0":
                for k in [0, 1]:
                    d_.append(int(a)*10+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return
            elif a[-1]=="9":
                for k in [8, 9]:
                    d_.append(int(a)*10+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return 
            else:
                for k in [-1, 0, 1]:
                    d_.append(int(a)*10+int(a[-1])+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return
        d.append(d_)
if K <= 9:
    print(K)
else:
    cal()

Measured memory_bytes: 7204
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 1e3+5;
const int INF = 0x3f3f3f3f;

int dp[50][N],v[50];
int h,w,k;

//void print(int n,int cnt){
//	printf("%d    ",n);
//	for(int i = 1;i < cnt;++i) printf("%d ",ss[i]);
//	printf("\n");
//}

inline int check(int cnt){
	int res = 0,lastline = 0;
	for(int i = 1;i <= w;++i){
		int Max = 0;
		for(int j = 1;j < cnt;++j){
			int t = dp[v[j]][i]-dp[v[j-1]][i]-dp[v[j]][lastline]+dp[v[j-1]][lastline];
			if(t > k && i-lastline == 1) return INF;
			Max = max(Max,t);
		}
		
		if(Max > k){
			res++;
			lastline = i-1;
		}
	}
	return res;
}

int main()
{
	scanf("%d%d%d",&h,&w,&k);
	for(int i = 1;i <= h;++i)
		for(int j = 1;j <= w;++j)
			scanf("%1d",&dp[i][j]),dp[i][j] += dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];		
	
	int ans = h+w-2,cnt;
	for(int i = 0;i < (1 << (h-1));++i){
		cnt = 0;
		v[cnt++] = 0;
		for(int j = 0;j < h-1;++j)
			if((1 << j) & i) v[cnt++] = j+1;
		v[cnt++] = h;
		
		if(cnt-2 >= ans) continue;
		//printf("%d %d\n",i,check(cnt)+cnt-2);
		ans = min(ans,check(cnt)+cnt-2);
	}
	printf("%d\n",ans);
    return 0;
}

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


int main(){
  int n;
  cin >> n;
  vector<int> d(n);
  rep(i,n) cin >> d[i];

  sort(d.begin(), d.end());
  int k = d[n/2] - d[n/2-1];
  cout << k << endl;
  return 0;
}


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

using namespace std;
typedef long long int ll;

struct LazySegmentTree{
private:
    int n; //葉の数
    vector<ll> node, lazy; //普通のセグ木の配列と遅延配列

public:
    LazySegmentTree(){}
    LazySegmentTree(vector<ll> v){
        int sz = v.size();
        int height = ceil(log2(sz));
        n = pow(2, height);
        node.resize(2*n-1, 0);
        lazy.resize(2*n-1, 0);

        for(int i = 0; i < sz; i++) node[i+(n-1)] = v[i];
        for(int i = n-2; i >= 0; i--) node[i] = node[(i<<1) + 1] + node[(i<<1) + 2];
    }

    void eval(int k, int l, int r){
        if(lazy[k] != 0){
            node[k] += lazy[k];

            if(r-l > 1){
                lazy[(k<<1)+1] += lazy[k]/2;
                lazy[(k<<1)+2] += lazy[k]/2;
            }
        }
        lazy[k] = 0;
    }

    ll getsum(int a, int b, int k=0, int l=0, int r=-1){
        if(r < 0) r = n;
        //区間に交わりが無い -> 0を返す
        if(b <= l || r <= a) return 0;

        eval(k, l, r);
        //区間を全て覆う -> その区間和を返す
        if(a <= l && r <= b) return node[k];
        //区間に一部交わりがある
        else{
            ll vl = getsum(a, b, (k<<1)+1, l, (l+r)/2);
            ll vr = getsum(a, b, (k<<1)+2, (l+r)/2, r);
            return vl+vr;
        }
    }
    void update(int a, int b, ll v, int k=0, int l=0, int r=-1){
        if(r < 0) r = n;
        //[a,b)にvを足すクエリ
        eval(k, l, r);
        if(b <= l || r <= a) return;
        else if(a <= l && r <= b){
            lazy[k] += (r-l)*v;
            eval(k, l, r); //アクセス後はlazy[k]=0のはずなので、(r-l)*vを足した後に評価が必要
        }
        else{
            update(a, b, v, (k<<1)+1, l, (l+r)/2);
            update(a, b, v, (k<<1)+2, (l+r)/2, r);
            node[k] = node[(k<<1)+1] + node[(k<<1)+2];
        }
    }
};

int main(void){
    int n, q; cin >> n >> q;
    vector<ll> A(n, 0);
    LazySegmentTree lst(A);
    for(int i = 0; i < q; i++){
        int cmd; cin >> cmd;
        if(cmd == 0){
            int s, t; ll x; cin >> s >> t >> x;
            lst.update(s-1, t, x);
        }
        else{
            int s, t; cin >> s >> t;
            cout << lst.getsum(s-1, t) << endl;
        }
    }
}


Measured memory_bytes: 8916
n = int(input())
a = list(map(int, input().split()))
ans = a[0]
l = []

for i in range(1, n, 2):
    ans -= a[i]
    ans += a[i + 1]

l.append(ans)

for i in range(n - 1):
    ans = a[i]*2 - ans
    l.append(ans)

print(*l)

Measured memory_bytes: 20536
N = gets.to_i
C = gets.split.map(&:to_i)

MOD = 10 ** 9 + 7
ans = 0

C.sort.reverse_each.with_index(1) do |c, i|
  ans += c * (i + 1)
  ans %= MOD
end

puts (4.pow(N - 1, MOD) * ans) % MOD


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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    multiset<int> s;
    for(int i = 0; i < n; i++) {
        s.insert(a[i] - 1);
        s.insert(a[i]);
        s.insert(a[i] + 1);
    }
    int cnt = 1, ans = 1;
    vector<int> b(s.begin(), s.end());
    for(int i = 0; i < (int) b.size() - 1; i++) {
        if(b[i] == b[i + 1]) ++cnt;
        else ans = max(ans, cnt), cnt = 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 18712
#include <iostream>
#include <vector>
#include <algorithm>
#define INF -1 * (1 << 30)

using namespace std;

int num;

int Search(vector<int> &f, vector<vector<int>> &p, int x, int t) {
	if (t == 10) {
		if (x == 0)
			return INF;
		int n, d, ans = 0;
		for (int i = 0; i < num; i++) {
			d = 0;
			n = x & f[i];
			while (n > 0) {
				if (n & 1)
					d++;
				n >>= 1;
			}
			ans += p[i][d];
		}
		return ans;
	}
	int ans = Search(f, p, x << 1, t + 1);
	ans = max(ans, Search(f, p, (x << 1) + 1, t + 1));
	return ans;
}

int main(void) {
	int i = 0, j, buf, ans;
	cin >> num;
	vector<int> f(num, 0);
	vector<vector<int>> p(num, vector<int>(11));
	for (; i < num; i++) {
		for (j = 0; j < 10; j++) {
			scanf("%d", &buf);
			if (buf)
				f[i] += 1 << j;
		}
	}
	for (i = 0; i < num; i++)
		for (j = 0; j < 11; j++)
			scanf("%d", &p[i][j]);
	ans = Search(f, p, 0, 0);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func next() int {
	sc.Scan()
	val, err := strconv.Atoi(sc.Text())
	if err != nil {
		fmt.Println(err)
		os.Exit(1)
	}
	return val
}

func main() {
	sc.Split(bufio.ScanWords)

	N, Y := next(), next()

	x, y, z := 0, 0, 0
	result := false
	for i := 0; i < N+1; i++ {
		for j := 0; j < N+1; j++ {
			k := N - i - j
			if k >= 0 {
				val := 10000*i + 5000*j + (N-i-j)*1000
				if val == Y {
					x = i
					y = j
					z = N - i - j
					result = true
					goto BREAK
				}
			}
		}
	}
	fmt.Println(-1, -1, -1)
BREAK:
	if result {
		fmt.Println(x, y, z)
	}
}

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

const int MOD = (int)1e9+7;

int main(){
  int N,x;
  cin >> N >> x;
  vector<int> a(N);
  for(int i=0;i<N;i++)  cin >> a.at(i);

  sort(a.begin(),a.end());
  int ans=0;
  for(int i=0;i<N-1;i++){
    x-=a.at(i);
    if(x>=0) ans++;
    else  break;
  }
  if(x==a.at(N-1))  ans++;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n,m;
    int b= 0,c = 0;
    cin >> n >> m;
    int a[100002] = {};
    int e[100002] = {};
    for(int i=0;i<m;i++){
       long long  int temp;
        string s;
        cin >> temp >>s;
        if(s == "WA" && a[temp] == 0){
            e[temp]++;
        }else if(s == "AC" && a[temp] == 0){
            a[temp] = 1;
            c++;
        }
    }
    
    for(int i=0;i<100002;i++){
        if(a[i] == 1 && e[i] != 0){
            b += e[i];
        }
    } 
    cout << c << " " << b << endl;
    return 0;
}



Measured memory_bytes: 1656
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
    class Program
    {
        static void Main(string[] args)
        {
            var str = Console.ReadLine().ToArray();
            int n = str.Length;
            int num = 0;
            for(int i = 0; i < n / 2; i++)
            {
                if (str[i] != str[n - 1 - i])
                {
                    num++;
                }
            }
            Console.WriteLine(num);
        }
        
    }
}


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

int main(){
	int n;
	cin >> n;
	vector<vector<int> > adj(n*n);
	for(int i=0; i<2*n*n-2*n; i++){
		int a,b;
		cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	vector<vector<int> > ans(n, vector<int>(n));
	for(int i=0; i<n*n; i++){
		if((int)adj[i].size() == 2){
			ans[0][0] = i;
			ans[0][1] = adj[i][0];
			ans[1][0] = adj[i][1];
			break;
		}
	}
	for(int i=2; i<n; i++){
		for(int next: adj[ans[0][i-1]]){
			if(next != ans[0][i-2] and (int)adj[next].size() < 4){
				ans[0][i] = next;
				break;
			}
		}
		for(int next: adj[ans[i-1][0]]){
			if(next != ans[i-2][0] and (int)adj[next].size() < 4){
				ans[i][0] = next;
				break;
			}
		}
	}

	for(int i=1; i<n; i++){
		for(int j=1; j<n; j++){
			for(int k: adj[ans[i][j-1]]){
				for(int l: adj[ans[i-1][j]]){
					if(k == l and k != ans[i-1][j-1]){
						ans[i][j] = k;
					}
				}
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cout << ans[i][j]+1 << " ";
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3488
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll n, a, b;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> a >> b;
	if(a > b){
		cout << 0 << endl;
		return 0;
	}
	else{
		if(n==1 && a!=b){
			cout << 0 << endl;
			return 0;
		}
		else{
			cout << (n-1)*b+a - ((n-1)*a+b) + 1 << endl;
			return 0;
		}
	}
}


Measured memory_bytes: 256
s = input()
nocounter = 0
n = len(s)
 
for i in range(n):
  if (i % 2 == 0):
    if s[i] == "L":
      print("No")
      nocounter = 1
      break
  if (i % 2 == 1):
    if s[i] == "R":
      print("No")
      nocounter = 1
      break
      
if (nocounter == 0):
  print("Yes")

Measured memory_bytes: 3060