akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 998244353;
ll dp[3010][3010];
ll A,B,C,D;
int main() {
    cin >> A >> B >> C >> D;
    dp[A][B] = 1;
    for (int i = A; i <= C; i++) {
        for (int j = B; j <= D; j++) {
            dp[i][j] += dp[i-1][j] * j;
            dp[i][j] %= mod;
            dp[i][j] += dp[i][j-1] * i;
            dp[i][j] %= mod;
            dp[i][j] -= dp[i-1][j-1] * (i - 1) % mod * (j - 1) % mod;
            if (dp[i][j] < 0)
                dp[i][j] += mod * mod;
            dp[i][j] %= mod;
        }
    }
    cout << dp[C][D] << endl;
    return 0;
}

Measured memory_bytes: 73952
# -*- coding: utf-8 -*-
n, m, q = map(int, input().split())
integer_set = [list(map(int, input().split())) for _ in range(q)]
a = [1]
score = 0

# 深さ優先探索(Depth First Search)
def dfs(seq):
    if len(seq) == n:
        global score
        tmp_score = 0
        for a, b, c, d in integer_set:
            if seq[b-1] - seq[a-1] == c:
                tmp_score += d
            else:
                tmp_score += 0
        score = max(score, tmp_score)
    else:
        for i in range(seq[-1], m+1):
            tmp_seq = seq.copy()
            tmp_seq.append(i)
            dfs(tmp_seq)

dfs(a)
print(score)


Measured memory_bytes: 9148
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

inline int gi()
{
	int f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

inline LL gl()
{
	LL f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int N = 200003, mod = 1000000007;

int n, m;
int a[N];
char s[N];

int main()
{
    n = gi();
    double ans = acos(-1) * 2 * n;
    printf("%.13lf\n", ans);
    return 0;
}


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

int main(){
  int X,Y;
  cin>>X>>Y;
  bool flag=false;
  for(int i=0;i<=X;++i){
    if(2*i+4*(X-i)==Y){
      flag=true;
    }
  }

  if(flag) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

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

vector<int> v(pow(2,18)+1,0),w(pow(2,18)+1,0);
vector<vector<int>> dp(512,vector<int>(1e5+1,0));

int dfs(int V,int W,int C){
  if(W<0){
    return 0;
  }
  if(V<512){
    return dp[V][W]+C;
  }
  int s=dfs(V/2,W-w[V],C+v[V]),t=dfs(V/2,W,C);
  return max(s,t);
}

int main() {
  int N;
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> v[i+1] >> w[i+1];
  }
  for(int i=1;i<512;i++){
    for(int j=1;j<1e5+1;j++){
      if(i>N){
        continue;
      }
      if(j>=w[i]){
        dp[i][j]=max(dp[i/2][j],dp[i/2][j-w[i]]+v[i]);
      }
      else{
        dp[i][j]=dp[i/2][j];
      }
    }
  }
  int q;
  cin >> q;
  for(int i=0;i<q;i++){
    int V,W;
    cin >> V >> W;
    cout << dfs(V,W,0) << endl;
  }
}

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

#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;

const ll MOD = 1000000007;
const long double EPS = 1e-10;
const int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    int cnt = 0;
    for(int i=0;i<n;++i) cnt += int(s[i] == 'R');

    cout << ((cnt>n-cnt)?"Yes":"No") << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
    string s;
    cin >> s;
    int times = 0;
    int length = s.length();
    for (int i=0; i < length/2; i++){
        if (s[i] != s[length-i-1]){
            times += 1;
        }
    }
    cout << times << endl;
}

Measured memory_bytes: 256
# 2018/12/22
# CADDi2018 for Beginners D

# Input
n = int(input())

awin_flg = False
for idx in range(n):
    wa = int(input())
    if (wa % 2) == 1:
        awin_flg = True

# Output
if awin_flg:
    print("first")
else:
    print("second")


Measured memory_bytes: 3188
N, M, K=map(int,input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
LA = [0]
LB = [0]
for i in range(N):
    C=LA[i]+A[i]
    if C>K:
        N=i
        break
    else:
        LA.append(C)
for j in range(M):
    C=LB[j]+B[j]
    if C>K:
        M=j
        break
    else:
        LB.append(C)
r=N
for i in range(N+1):
    u=0
    for j in range(r-N+i,M+1):
        if LA[N-i]+LB[j]>K:
            r=max(r,N-i+j-1) # 最大のrを求めたいので結果をrefineする場合だけで回す
            u=1
            break
    if u==0:
        r=max(r,N-i+M)
        break
print(r)


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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    int N,M,Q; cin>> N >> M >> Q;
    vector<vector<int>> train(N+1, vector<int>(N+1,0));
    REP(i,M){
        int l,r; cin >> l >> r;
        train[l][r] ++;
    }

    REP(i,N+1){
        REP(j,N){
            train[i][j+1] += train[i][j];
        }
    }

    for(int i=N; i>=1; i--){
        REP(j,N+1){
            train[i-1][j] += train[i][j];
        }
    }

    REP(i,Q){
        int p,q; cin >> p >> q;
        cout << train[p][q] << endl;
    }

    return 0;
}

Measured memory_bytes: 4584
#include<stdio.h>
#include<string.h>

int main()
{
  int n;
  char s[100]={};
  int i;
  int x=0;
  int max;
  
  scanf("%d",&n);  
  scanf("%s",s);
  
  max=x;
  for(i=0;i<strlen(s);i++)
  {
    if(s[i]=='I')
    {
      x++;
    }
    else if(s[i]=='D')
    {
      x--;
    }
    
    if(max<x)
    {
      max=x;
    }
  }
  
  printf("%d\n",max);
  
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define vi vector<int>
#define vl vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define abu ios_base::sync_with_stdio(0)
#define said cin.tie(0)
using namespace std;
ll const MOD = 998244353;

void yes(){
    cout<<"YES"<<'\n';
}

void no(){
    cout<<"NO"<<'\n';
}

ll fact(int n){
    ll ans = 1;
    for(int i=2;i<=n;i++){
        ans = (ans*i)%MOD;
    }

    return ans;
}

ll powM(int n, int x){
    if(x==0){
        return 1;
    }
    if(x==1){
        return n%MOD;
    }

    if(x%2==0){
        ll a = powM(n,x/2);
        return (a*a)%MOD;
    }else{
        return (n*powM(n,x-1))%MOD;
    }
}

ll C(int n, int k){
    return (fact(n) * powM((fact(k)*fact(n-k))%MOD,MOD-2))%MOD;
}

ll A(int n, int k){
    return (fact(n) * powM(fact(n-k)%MOD,MOD-2))%MOD;
}

ll dp[100100];


void solve(){
    ll n,W;
    cin>>n>>W;
    for(int i=0;i<n;i++){
        int v,w;
        cin>>w>>v;
        for(int i = W-w;i>=0;i--){
            dp[i+w] = max(dp[i+w],dp[i]+v); 
        }
    }

    ll mx = 0;
    for(int i=0;i<=W;i++){
        mx = max(dp[i],mx);
    }
    cout<<mx<<'\n';
}

int main(){
    abu;
    said;
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }

    return 0;
}


Measured memory_bytes: 1024
M, D = map(int, input().split())

count = 0
for i in range(1,M+1):
    for j in range(22,D+1):
        if int(str(j)[1]) >= 2:
            if int(str(j)[0]) >= 2:
                if int(str(j)[0]) * int(str(j)[1]) == i:
                    count += 1
print(count)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
ll gcd(ll a,ll b){return a?gcd(b%a,a):b;}
// なるべく上限付きLCM使おう
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/

int N, P[20];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> P[i];

    int ans = 0;
    rep(msk, 1, 1 << N) {
        ll lc = 1;
        rep(i, 0, N) if (msk & (1 << i)) lc = lcm(lc, P[i]);
        bool ok = true;
        rep(i, 0, N) if (!(msk & (1 << i))) if (lc % P[i] == 0) ok = false;
        if (ok) ans++;
    }
    cout << ans << endl;
}



Measured memory_bytes: 3156
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<deque>

using namespace std;

void MakePrimeArray(deque<bool>& A,int n){
	
	A[0] = A[1] = false;
	for(int i=2;i<n;i++){
		A[i] = true;
	}
	
	for(int	i=2;i*i<n;i++){
	if(A[i]){
			for(int j=i*i;j<n;j+=i){
				A[j] = false;
			}
		}
	}
	
}

inline int GoldBach(const deque<int>& prime,int n){
	
	int count=0;
	deque<int> clear;
	bool ok=true;
	
	for(int i=0;prime[i]<n;i++){

		if(std::binary_search(clear.begin(), clear.end(), prime[i])){
			break;
		}
		
		int num=n-prime[i];
		
	
		if(std::binary_search(prime.begin(), prime.end(), num)){
			count++;	
			clear.insert(clear.begin(),num);
		}
		
	}
	return count;
}

int main(){
	
	int n=50001;

	deque<bool> primearray;
	
	primearray.resize(n);
	
	MakePrimeArray(primearray,n);
	
	deque<int> prime;
	
	for(int i=2;i<n;i++){
		if(primearray[i]){
			prime.push_back(i);
		}
	}
	
	
	while(true){
		int innum;
		cin >> innum;
		//scanf("%d",&innum);
		
		if(innum==0) break;
		int answer = GoldBach(prime,innum) ;
		//printf("%d \n",answer);
		cout << answer << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3228
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 1010


int main(){
  int n;
  int f[SIZE][5][2];
  int p[SIZE][SIZE];
  
  scanf("%d",&n);

  for(int i=0;i<n;i++){
    for(int j=0;j<5;j++){
      scanf("%d%d",f[i][j]+0, f[i][j]+1);
    }
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<=10;j++){
      scanf("%d",p[i]+j);
    }
  }

  ll ans = -LLINF;
  
  for(int i=1;i<(1<<10);i++){
    ll calc = 0;

    for(int j=0;j<n;j++){
      int cc = 0;
      for(int k=0;k<10;k++){
        cc += (i & (1 << k)) && f[j][k/2][k%2];
      }

      calc += p[j][cc];
    }

    ans = max(ans, calc);
  }

  printf("%lld\n",ans);
  
  
  return 0;
}



Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long int
#define fi first
#define se second
#define pub push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for(int i=(int)(l);i<(int)(r);i++)
#define repd(i, l, r) for (int i=(int)(l);i>=(int)(r);i--)
#define clrg(i, l, r) for(int i=(int)(l);i<(int)(r);i++)vis[i]=0,v[i].clear();
int power(int x, unsigned int y){int res = 1;while (y > 0){ if (y & 1){res = res*x;} y = y>>1;x = x*x;}return res;}
int powermod(int x, unsigned int y, int p){int res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1; x = (x*x) % p;}return res;}
#define print2d(mat,n,m){for(int i=0;i<(int)(n);i++){for(int j=0;j<(m);j++){cout<<mat[i][j]<<" ";}cout<< endl;}}
#define clr(a,x) memset(a,x,sizeof(a))
#define rr(v) for(auto &val:v)
#define print(v) for (const auto itr : v){cout<<itr<<' ';}cout<<"\n";
#define ln length()
#define sz size()
#define mod 1000000007
#define elif else if
int32_t main(){
   int n; cin>>n;
   int m=n;
   int x=0;
   while(n-3>=3){
     n-=3;
     x++;
   }
   if(n>=3)x++;
   vector<int> fact(m+1);
   fact[0]=1;
   rep(i,1,m+1){
     fact[i]=(fact[i-1]*i)%mod;
   }
   int ans=0;
   rep(i,1,x+1){
      int rem=m-i*3;
      int in=(fact[i+rem-1]*powermod((fact[rem]*fact[i-1])%mod,mod-2,mod))%mod;
      ans+=in;
      ans%=mod;
   }
   cout<<ans<<"\n";
   return 0;
}
/*
Edge cases? n=1? a[i]<=0?
long vs int? 1LL? 64bits?
Re-read problem. Is it as easy as it seems?
KEEP CORRECTING AND SUBMITTING!
*/


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	string s;
	map<string,int>mp;
	for(int i=0;i<n;i++){
		cin>>s;
		mp[s]++;
	}
	cin>>n;
	while(cin>>s)
		mp[s]--;
	int ans=0;
	for(auto x:mp)
		ans=max(ans,x.second);
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll, ll> P;
int main() {
	int n;
	cin >> n;
	vl x(n);
	vl y(n);
	cin >> x[0];
	for (int i = 1; i < n; i++) {
		cin >> x[i];
		y[i-1] = x[i]-x[i-1];
	}
	int m;
	cin >> m;
	ll k;
	cin >> k;
	vi a(m);
	
	for (int i = 0; i < m; i++) {
		int t;
		cin >> t;
		t--;
		a[i] = t;
	}
	vi z(n - 1);
	for (int i = 0; i < n - 1; i++) z[i] = i;
	for (int i = 0; i < m; i++) {
		swap(z[a[i]],z[a[i]-1]);
	}
	//for (int i = 0; i < n - 1; i++) cout << z[i] << " "; cout << endl;
	vi w(n - 1);
	for (int i = 0; i < n - 1; i++) w[i] = i;
	while (k > 0) {
		if (k % 2 == 1) {
			for (int i = 0; i < n-1; i++) {
				w[i] = z[w[i]];
			}
		}
		vi r(n - 1);
		r = z;
		for (int i = 0; i < n - 1; i++) {
			z[i] = r[r[i]];
		}
		k = k / 2;
	}
	//for (int i = 0; i < n - 1; i++) cout << w[i] << " "; cout << endl;

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

Measured memory_bytes: 4344
#include <iostream>
#include <vector>
using namespace std;
struct UF{
    int par[200000];
    int rank[200000];
    int g[200000];

    void init(int n){
        for(int i=0;i<n;i++){
            par[i]=i;
            rank[i]=0;
            g[i]=1;
        }
    }

    int find(int x){
        if(par[x]==x)return x;
        return par[x]=find(par[x]);
    }

    void unite(int x, int y){
        x=find(x);
        y=find(y);
        if(x!=y){
            if(rank[x]<rank[y]){
                par[x]=y;
                g[y]+=g[x];
                g[x]=0;
            }else{
                par[y]=x;
                if(rank[x]==rank[y])rank[x]++;
                g[x]+=g[y];
                g[y]=0;
            }
        }
    }

    bool same(int x, int y){
        return find(x)==find(y);
    }
};

int main(void){
    int n, m;
    UF u;
    cin >> n >> m;
    u.init(n+m);
    for(int i=0;i<n;i++){
        int k;
        cin >> k;
        for(int j=0;j<k;j++){
            int l;
            cin >> l;
            u.unite(i, n+l-1);
        }
    }
    for(int i=0;i<n;i++){
        if(u.find(i) != u.find(0)){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
 int N;
  cin >>N;
  vector<int> vec(N);
  rep(i,N) {
cin >>vec.at(i);
  }

  
  int count=1;
  int max=vec.at(0);
  repl(i,1,N) {
    if((vec.at(i))>=max) {
      count++;
      max=vec.at(i);
      
    }
  }
  cout <<count<< endl;
}
      


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

const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;

using namespace std;

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b,c;
	cin >> a >> b >> c;
	if(a+b+c >=22)cout << "bust"<<endl;
	else cout << "win" << endl;
}

Measured memory_bytes: 256
use std::io::stdin;

fn main() {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    let a: Vec<usize> = s
        .split_whitespace()
        .map(|e| e.parse::<usize>().unwrap())
        .collect();
    let max = *a.iter().max().unwrap();
    let others = a.iter().sum::<usize>() - max;

    println!("{}", if max == others { "Yes" } else { "No" });
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
 
using namespace std;

 
const int MAX_N = int(1e6) + 10;
const long long int MOD=1e9+7;
const long long int INF=1e18;
 
typedef long long int ll;
typedef unsigned long long int llu;
 
 
 
inline ll mul(ll a,ll b){
 
    a=(a+MOD)%MOD;
    b=(b+MOD)%MOD;
    ll c=a*b;
    c=(c+MOD)%MOD;
    return c;
}
inline ll add(ll a,ll b){
    a=(a+MOD)%MOD;
    b=(b+MOD)%MOD;
    ll ans=(a+b);
    ans=(ans+MOD)%MOD;
    return ans;
}
ll power(ll a,ll b,ll c=0){
    ll ans=1;
    while(b){
        if(b&1){
            ans=mul(ans,a);
        }
        a=mul(a,a);
        b=b/2;
    }
    return ans;
}
 
  
 
 
#define all(x) (x).begin(),(x).end()




//s.reserve(32768); //updated !
//s.max_load_factor(0.25);





ll fun(ll k,vector<ll>&pref){
    int low=0;
    int high=(int)pref.size()-1;
    ll ans=-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(pref[mid]<=k){
            ans=mid;
            low=mid+1;
        }else{
            high=mid-1;
        }
    }

    return ans+1;
}



ll n,m,k;
ll ans=0;




int main(){
   
   cin>>n>>m>>k;

   vector<ll>a(n);
   vector<ll>b(m);
   vector<ll>pref(m);

   for(int i=0;i<n;i++){
    cin>>a[i];
   }

   for(int i=0;i<m;i++){
    cin>>b[i];
   }

   pref[0]=b[0];

   for(int i=1;i<m;i++){
    pref[i]=b[i]+pref[i-1];
   }

   ans=0;

   ans=fun(k,pref);

   for(int i=0;i<n;i++){
    k-=a[i];
    if(k>=0){
        ans=max(ans,i+1+fun(k,pref));
    }
   }

   cout<<ans;
    
}


 
    



    



    
    
    




    


    

    






    
    

    
 
    
 

 
 
    
 
 


Measured memory_bytes: 7984
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
// #pragma GCC optimize("O2")
typedef long long int ll;
typedef long double ld;
typedef map <ll,ll> mm;
typedef vector <ll> mv;
typedef pair <ll,ll> mp;
typedef set <ll> ms;
typedef multiset <ll> mms;
typedef queue <ll> mq;
typedef deque <ll> mdq;
typedef stack <ll> mst;
typedef priority_queue <ll> mpq;
typedef priority_queue <ll, vector<ll>, greater<ll> > mmh;
typedef complex<double> cd;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define flush cout.flush();
#define all(v) v.begin(),v.end()
#define deb(x) cout << #x << " " << x << endl;
#define ff first
#define ss second
#define pb(v) push_back(v)
#define lb(v) lower_bound(v)
#define ub(v) upper_bound(v)
#define cn continue
#define forl(i,n) for(ll i=0;i<n;i++)
#define forlr(i,n) for(ll i=n-1;i>=0;i--)
#define rev(s) reverse(s.begin(),s.end())
void swap(ll &a,ll &b) {
	ll tmp=a;
	a=b;
	b=tmp;
}
ll atoistring(string s) {
	stringstream lol(s);
	ll x;
	lol>>x;
	return x;
}
void pv(mv v) {
	forl(i,v.size()) cout<<v[i]<<" ";
	cout<<"\n";
}
void pa(ll *v, ll size) {
	forl(i,size) cout<<v[i]<<" ";
	cout<<"\n";
}
void removeDups(mv &v) {
	sort(all(v));
	mv::iterator it = unique(v.begin(), v.end());
	v.resize(distance(v.begin(), it));
}
inline ld kthRoot(ld n, ll k) {
	return pow(k, (1.0 / k) * (log(n) / log(k)));
}
ll power(ll x, ll y, ll p) {
	ll res=1;
	x=x%p;
	while(y>0) {
		if(y&1) res = (res*x)%p;
		y=y>>1;
		x=(x*x)%p;
	}
	return res;
}
void checkmod(ll &x, ll mod) {
	if(x>=mod) x%=mod;
}

ll mod = 1e9 + 7;

ll arr[200005];
void thisIsMain() {
	ll n;
	cin>>n;
	forl(i,n) cin>>arr[i];
	ll ans = 0;
	for(ll i=1;i < n ;i ++ ) {
		if(arr[i] >= arr[i - 1]) cn;
		else {
			ans += arr[i - 1] - arr[i];
			arr[i] = arr[i - 1];
		}
	}
	cout<<ans<<"\n";
}

int main(void)
{
	fastio
	ll t = 1;
	// cin>>t;
	while(t--) thisIsMain();
	return 0;
}

Measured memory_bytes: 5180
from fractions import gcd
#from math import gcd
N,X = map(int,input().split())
x = list(map(int,input().split()))
dif = [abs(x[i+1]-x[i]) for i in range(N-1)]
ans = abs(x[0]-X)
for i in range(N-1):
    ans = gcd(ans,dif[i])
print(ans)


Measured memory_bytes: 16280
#include <stdio.h>
 
int main(int argc, const char * argv[])
{
    int i,j,m,n,card[4][14];
    char x;
     
    for(i=0;i<4;i++){
        for(j=1;j<14;j++){
            card[i][j]=0;
        }
    }
     
    scanf("%d",&n);
     
    for(i=0;i<n;i++){
        scanf("%s",&x);
        scanf("%d",&j);
         
        if(x=='S'){
            m=0;
        }else if(x=='H'){
            m=1;
        }else if(x=='C'){
            m=2;
        }else if(x=='D'){
            m=3;
        }
        card[m][j]=1;
    }
    for(i=0;i<4;i++){
        for(j=1;j<14;j++){
            if(card[i][j]==0){
                if(i==0){
                    printf("S %d\n",j);
                }else if(i==1){
                    printf("H %d\n",j);
                }else if(i==2){
                    printf("C %d\n",j);
                }else if(i==3){
                    printf("D %d\n",j);
                }
            }
        }
    }
    return 0;
}

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

#define ll long long int
#define MD 1000000007

int N;
ll A[55][55], R[55][55], H[55][55];

void mul(ll M1[][55], ll M2[][55])
{
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
    {
        H[i][j] = 0;
        for (int k = 0; k < N; k++) H[i][j] = (H[i][j] + M1[i][k] * M2[k][j]) % MD;
    }
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) M1[i][j] = H[i][j];
}

void fastpow(ll p)
{
    while (p)
    {
        if (p % 2) mul(R, A);
        mul(A, A);
        p /= 2;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll K;
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        R[i][i] = 1;
        for (int j = 0; j < N; j++) cin >> A[i][j];
    }
    fastpow(K);
    ll res = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) res = (res + R[i][j]) % MD;
    cout << res << '\n';
    return(0);
}

Measured memory_bytes: 384
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let h: i32 = read();
    let w: i32 = read();
    let mut field = vec![];
    for _y in 0..h {
        let s = read::<String>().chars().collect::<Vec<_>>();
        field.push(s);
    }
    for y in 0..h {
        for x in 0..w {
            if field[y as usize][x as usize] == '#' {
                continue;
            }
            let mut sum = 0;
            for dy in [-1, 0, 1].iter() {
                for dx in [-1, 0, 1].iter() {
                    let ny = y + dy;
                    let nx = x + dx;
                    if ny < 0 || ny >= h || nx < 0 || nx >= w
                        || field[ny as usize][nx as usize] != '#'
                    {
                        continue;
                    }
                    sum += 1;
                }
            }
            field[y as usize][x as usize] = ('0' as u8 + sum as u8) as char;
        }
    }
    for y in 0..h {
        for x in 0..w {
            print!("{}", field[y as usize][x as usize]);
        }
        println!("");
    }
}


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

int main(){
    int N, A[100000], B[100000];
    cin >> N;
    for(int i=0; i<N; i++) cin >> A[i];
    for(int i=0; i<N; i++) cin >> B[i];

    vector<int> over;
    int64_t sum = 0, lack = 0;
    int ans = 0;
    for(int i=0; i<N; i++){
        sum += A[i] - B[i];
        if(A[i] > B[i]){
            over.push_back(A[i] - B[i]);
        }else if(A[i] < B[i]){
            ans++;
            lack += B[i] - A[i];
        }
    }

    if(sum < 0){
        cout << -1 << endl;
        return 0;
    }

    sort(over.rbegin(), over.rend());
    for(auto a : over){
        if(lack <= 0) break;
        lack -= a;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <deque>
#include <climits> 



int main()
{
    long A,B;
    std::cin >> A >> B;
    if(A<=9 && B<=9){
        std::cout << A*B << std::endl;
    }else{
        std::cout << -1 << std::endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int num;
map<int, int>mp;
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		mp[x]++;
	}
	int x = 0;
	for (auto it : mp) {
		x ^= it.first;
		num++;
	}
	if (num == 1) {
		cout <<( mp[0] == n ? "Yes\n" : "No\n");
	}
	else if (n % 3 != 0) {
		cout << "No" << '\n';
	}
	else if (num == 2) {
		if (mp[0] == n / 3) cout << "Yes" << '\n';
		else cout << "No" << '\n';
	}
	else if (num == 3 && x == 0) {
		for (auto it : mp) {
			if (it.second != n / 3) { puts("No"); return 0; }
		}
		puts("Yes");
	}
	else cout << "No" << '\n';
}




Measured memory_bytes: 3840
#include <iostream>

using namespace std;

int main() {
  // input
  int a;
  cin >> a;
  int L = a/100;
  int R = a%100;

  // solve
  string ans;
  if ((0<L && L<13) && (0<R && R<13)){
    ans = "AMBIGUOUS";
  }else if ((0<L && L<13) && (13<=R || R == 0)){
    ans = "MMYY";
  }else if ((0<R && R<13) && (13<=L || L == 0)){
    ans = "YYMM";
  }else{
    ans = "NA";
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
ans = 0 ;count = 0 ;pro = 1
mod=10**9+7
n=int(input())
A=list(map(int,input().split()))
C=collections.Counter(A)
if n%2==1:
    if C[0]!=1:
        print(0)
        exit()
    else:
        a=2
else:
    if C[1]!=2:
        print(0)
        exit()
    else:
        a=3
for i in range(a,n,2):
    if C[i]!=2:
        print(0)
        exit()
print(pow(2,n//2,mod))

    

Measured memory_bytes: 14568
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<ll, ll>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n, d;
    cin, n, d;
    int ans = 0;
    REP(i, 0, n) {
        ll x, y;
        cin, x, y;
        ans += x * x + y * y <= d * d;
    }
    print(ans);
    return 0;
}


Measured memory_bytes: 3652
#include <numeric>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <iostream>
#include <sstream>
#include <vector>
#include <cstdio>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <string>
#include <bitset>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <sstream>

using namespace std;

#ifdef LOCAL
#define logv(a) {cerr << #a << " = "; for (auto& e : a) {cerr << e << " ";} cerr << "\n";}
#define logvp(a) {cerr << #a << " = "; for (auto& e : a) {cerr << "(" << e.first << ", " << e.second << ") ";} cerr << "\n";}
#define logvv(a) {cerr << #a << " = \n"; for (auto& r : a) { for (auto& e : r) {cerr << e << " ";} cerr << "\n";} }
#define logvf(a, field) {cerr << #a"."#field << " = \n"; for (auto& e : a) { cerr << e.field << " ";} cerr << "\n"; }
#define logs(a) cerr << #a << " = " << (a) << "\n";
#define logss(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << "\n";
#define logp(a) cerr << #a << " = " << "(" << a.first << ", " << a.second << ")" << "\n";
#define cond(pred, stmt) if (pred) { stmt }
#else
#define logv(a)
#define logvp(a)
#define logvv(a)
#define logvf(a, field)
#define logs(a)
#define logss(a, b)
#define logp(a)
#define cond(pred, stmt)
#endif

#define forn(a, e) for (int a = 0; a < (int)e; a++)
#define forr(a, s, e) for (int a = s; a < (int)e; a++)

using i64 = long long;

template<typename T>
using Pair = array<T, 2>;

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

    string s;
    while (cin >> s) {
        map<char, vector<i64>> ps;
        map<char, i64> pos;
        forn(i, s.size()) {
            ps[s[i]].push_back(i);
            pos[s[i]] = ps[s[i]].front();
        }

        string t;
        cin >> t;

        i64 spos = 0;
        bool ok = true;
        forn(i, t.size()) {
            if (!ps.count(t[i])) {
                ok = false;
                break;
            }
            i64 cur = spos % s.size();
            auto& vps = ps[t[i]];
            auto next = lower_bound(vps.begin(), vps.end(), cur);
            if (next == vps.end()) {
                spos += s.size() - cur + vps.front();
            } else {
                spos += *next - cur;
            }
            spos++;
        }
        if (ok) {
            cout << spos << endl;
        }
        else {
            cout << -1 << endl;
        }
    }
}


Measured memory_bytes: 1616
D,G=map(int,input().split())

p=[0]*D
c=[0]*D

for i in range(D):
    p[i],c[i]=map(int,input().split())
ans=10e+9

for i in range(2**D):
    sum=0
    q=0
    for j in range(D):
        if(i>>j & 1):
            sum+=(j+1)*100*p[j]+c[j]
            q+=p[j]
        else:
            rest_max=j
    if(sum<G):
        r1=100*(rest_max+1)
        need=-(-(G-sum)//r1)
        if(need>p[rest_max]-1):
            continue
        q+=need
        sum+=need*r1
    
    if(sum>=G):
        ans=min(ans,q)

print(ans)

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

int main() {
  string S;cin>>S;
  int A=0; int B=0;
  for(int i =0; i< S.size(); i++){
    if(S.at(i) == '+'){
      A++;
    }
    else{
      B++;
    }
  }
  cout<<A-B<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define mk make_pair
#define pb push_back
#define ff first
#define ss second
#define ar array
#define del 1e-8

double pi=3.141592653589793238;
const int M = 1e9+7;
const int Nmax=5005;
const int MM = 998244353;
const int N=100001;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T=1;
	//cin>>T;
	while(T--){
      ll ans=0;
      int n;
      cin>>n;
      int arr[n];
      for(int i=0;i<n;i++){
        cin>>arr[i];
      }
      for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            for(int k=j+1;k<n;k++){
                if(arr[i]!=arr[j] && arr[j]!=arr[k] && arr[i]!=arr[k]){
                    if(arr[i]+arr[j]>arr[k] && arr[j]+arr[k]>arr[i] && arr[i]+arr[k]>arr[j])ans++;
                }
            }
        }
      }
    cout<<ans<<"\n";
	}
	return 0;
}


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

using namespace std;

const long long MOD = 1000000007LL;
long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n;

    long long a, b;

    cin >> n >> a >> b;

    for(int i = 1; i < n; ++i){
        long long c, d;
        cin >> c >> d;

        long long mini = max((a + c - 1) / c, (b + d - 1) / d);

        a = c * mini;
        b = d * mini;
    }

    cout << a + b;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int n,m;
int x[55],y[55],a[55],b[55];
int ans[55];
int main(void){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
    }
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=0;i<n;i++){
        int cnt=1000000000;
        for(int j=0;j<m;j++){
            if(cnt>abs(x[i]-a[j])+abs(y[i]-b[j])){
                ans[i]=j+1;
                cnt=abs(x[i]-a[j])+abs(y[i]-b[j]);
            }
        }
        cout<<ans[i]<<endl;
    }
    
    
}


Measured memory_bytes: 3604
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict, Counter
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

N = i_inpl()
F = []
for _ in range(N):
    Fi = l_inpl()
    F.append(Fi)

P = []
for _ in range(N):
    Pi = l_inpl()
    P.append(Pi)


# bit全探索
ans = -1 * INF
for i in range(1, 2**10):
    tmp = 0
    for j in range(N):
        c = 0
        # NOTE: iとF[j]のAND演算
        for k in range(10):
            if ((i>>k) & 1) & F[j][k]:
                c += 1
        tmp += P[j][c]
    ans = max(ans, tmp)

print(ans)

Measured memory_bytes: 42092
#include <stdio.h>
#include <stdlib.h>
 
#define NMAX 1000
 
int bs (int [], int, int);
 
int compar (const void *a, const void *b) {
  return *(int *)a- *(int *)b;
}
 
int main(void)
{
  while(1)
  {
  	int i,j,k,N,M,c,p[NMAX*NMAX],s;
  	scanf("%d%d",&N,&M);
	if(N==0 && M==0) break;
	for(i=0;i<=N-1;i++)
	{
		scanf("%d",&p[i]);
	}
	k=N;
	for(i=0;i<=N-1;i++)
	{
		for(j=i;j<=N-1;j++)
		{
			p[k]=p[i]+p[j];
			k++;
		}
	}
	p[k]=0;
	qsort(p,k+1,sizeof(int),compar);
	s=M;
	for(i=c=0;i<=k;i++)
	{;
		if(p[i]<=M)
		{
			s=p[i]+bs(p,k+1,M-p[i]);
			if(s<=M&&s>c)c=s;
		}
	}
	printf("%d\n",c);
  }
  return 0;
}
 
 int bs (int D[], int n, int c) 
 {
    int j,k,l;
    j=0;
    k=n-1;
    while(1)
	{
        if(j<=k)
		{
            l=(j+k)/2;
            if(D[l] > c)
            {
                k=l-1;
            }
            else if(D[l+1] < c)
            {
                j=l+1;
            }
            else
            {
                return D[l];
            }
		}
		else
		{
	        return D[k];
		}
    }
}

Measured memory_bytes: 5256
N = int(input())
a = []
b = []
a_max = 0
a_second = 0

for i in range(N):
    a.append(int(input()))

b = a[:]
a.sort(reverse=True)

a_max = a[0]
a_second = a[1]

for i in range(N):
    if b[i] == a_max:
        print(a_second)
    else:
        print(a_max)


Measured memory_bytes: 14112
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define RFOR(i,a,b) for(int i = (int)(b-1);i>=(int)(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " <<
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

signed main() {
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout.precision(20);

  int n;
  cin >> n;
  vector<P> p(n);
  REP(i,n){
    cin >> p[i].first >> p[i].second;
  }

  sort(p.begin(),p.end(),[](P a, P b){
    return a.second < b.second;
  });

  int time = 0;
  REP(i, n){
    if(time + p[i].first > p[i].second){
      cout << "No" << endl;
      return 0;
    }
    time += p[i].first;
  }

  cout << "Yes" << endl;

  return 0;
}

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

left = 0
right = 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j] and i < j:
            right += 1
        elif a[i] > a[j] and j < i:
            left += 1
print((right*k*(k+1)//2 + left*(k-1)*k//2) % (10**9+7))

Measured memory_bytes: 42604
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        C solver = new C();
        solver.solve(1, in, out);
        out.close();
    }

    static class C {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            int m = Integer.parseInt(in.next());

            if (n >= m) {
                out.println(0);
                return;
            }
            int[] x = new int[m];
            for (int i = 0; i < m; i++) {
                x[i] = Integer.parseInt(in.next());
            }
            Arrays.sort(x);
            int[] diff = new int[m];
            for (int i = 0; i < m - 1; i++) {
                diff[i] = Math.abs(x[i] - x[i + 1]);
            }
            Arrays.sort(diff);

            int tmp = 0;
            for (int i = 1; i < n; i++) {
                tmp += diff[m - i];
            }
            // 出力
            out.println(x[m - 1] - x[0] - tmp);

        }

    }
}



Measured memory_bytes: 46140
#include <iostream>
using namespace std;
int n,a[100][100],b[100],c[100],d[100],cnt=1;
void DepthFirstSearch(int now){
  b[now]=1;
  c[now]=cnt;
  cnt++;
    for(int i=0;i<n;i++){
        if(a[now][i] && b[i]!=1){
            DepthFirstSearch(i);
            cnt++;
        }
    }
  d[now]=cnt;
}
int main(){
  
  int u,m,num;
  cin>>n;
  for(int i = 0;i < n;i++){
    cin>>u>>m;
    for(int j = 0;j < m;j++){
      cin >> num;
      a[u-1][num-1]=1;
    }
  }
    for(int i=0;i<n;i++){
       if(b[i]!=1){
         DepthFirstSearch(i);
         cnt++;
       }
    }
  
    for(int i=0;i<n;i++){
        cout<< i+1 << " " << c[i] << " " << d[i]<<endl;
    }
  return 0;
  
}


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


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmpArray = br.readLine().split(" ");
		
		int h = Integer.parseInt(tmpArray[0]);
		int w = Integer.parseInt(tmpArray[1]);
		
		char[][] matrix = new char[h][w];
		int[][] numOfBomb = new int[h][w];
		
		int[] dx = {0,1,1,1,0,-1,-1,-1};
		int[] dy = {-1,-1,0,1,1,1,0,-1};
		for(int i = 0; i < h; i++){
			String input = br.readLine();
			for(int j = 0; j < w; j++){
				matrix[i][j] = input.charAt(j);
				
				//八方向に爆弾数加算
				if(matrix[i][j] == '#'){
					for(int k = 0; k < 8; k++){
						int x2 = j + dx[k];
						int y2 = i + dy[k];
						
						if(inRange(x2, y2, w, h) && matrix[y2][x2] != '#'){
							numOfBomb[y2][x2]++;
						}
					}
				}
			}
		}
		
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				if(matrix[i][j] == '.'){
					System.out.print(numOfBomb[i][j]);
				}
				else {
					System.out.print(matrix[i][j]);
				}
			}
			
			System.out.println();
		}
		
	}
	
	static boolean inRange(int x, int y, int w, int h){
		if(x < 0 || x >= w || y < 0 || y >= h){
			return false;
		}
		else return true;
	}

}


Measured memory_bytes: 25044
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include<complex>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repd(i, n) for (int i = n; i > 0; i--)
#define mod 1000000007
#define MOD 998244353
#define inf 1e20
typedef long long int ll;
typedef pair<ll, ll> pr;
typedef complex<double> com;


int main(){
	int n, m;
	cin >> n >> m;
	vector<string> a(n);
	vector<string> b(m);
	rep(i, n) {
		cin >> a[i];
	}
	rep(i, m) {
		cin >> b[i];
	}
	rep(i,n-m+1){
		rep(j, n - m + 1) {
			int cnt = 0;
			rep(k, m) {
				rep(l, m) {
					if (a[i + k][j + l] == b[k][l]) {
						cnt++;
					}
				}
			}
			if (cnt == m * m) {
				cout << "Yes";
				return 0;
			}
		}
	}
	cout << "No";
	return 0;
}
//Ctrl+Aを使わない

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long  k;
	cin>>k;
	string s;
	cin>>s;
	if(s.size()<=k){
		cout<<s<<endl;
	}else{
		for(int i=0;i<k;i++){
			cout<<s[i];
		}
		cout<<"..."<<endl;
	}
	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
using namespace std;
typedef long long ll;
 
int main(){
 ll n;
  cin>>n;
  ll val[n];
  rep(i, n){
cin>>val[i];}
  
  
  ll cnt=0;
  ll ptcnt=0;
  rep(i, n){
    if(val[i]!=0){
      ptcnt+=val[i];}
    else{
      cnt+=ptcnt/2;
      ptcnt=0;}
  }
  
  cnt+=ptcnt/2;
  
  cout<<cnt<<endl;
 
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

int main() {
  string n;
  cin >> n;
  ll sum = 0;
  for(char i : n){
    sum += i - '0';
  }
  if(sum % 9 == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3720
import java.util.HashMap;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s  = sc.next().toCharArray();
        boolean can = true;
        for(int i=0;i<s.length;i++){
            char tmp = s[i];
            if((i+1)%2==1){
                if(tmp=='R' || tmp=='U' || tmp=='D'){
                    continue;
                }
                can = false;
            }else{
                if(tmp=='L' || tmp=='U' || tmp=='D'){
                    continue;
                }
                can = false;
            }
            break;
        }
        if(can){
            System.out.println("Yes");                                                                                                                                                                                                                                          
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 25044