akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 3005
#define ll long long
#define mod 1000000007
#define inv2 500000004
void Read(int &p)
{
	p = 0;
	char c = getchar();
	for (; c < '0' || c > '9'; c = getchar());
	for (; c >= '0' && c <= '9'; c = getchar())p = p * 10 + c - '0';
}
int n, q;
int f[N][N], A[N];
int main()
{
	Read(n), Read(q);
	for (int i = 1; i <= n; i++)
		Read(A[i]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			f[i][j] = (A[i] > A[j]);
	int ans = 1;
	for (; q--; )
	{
		ans = (ans << 1) % mod;
		int x, y;
		Read(x), Read(y);
		for (int i = 1; i <= n; i++)
		{
			if (i != x && i != y)
			{
				f[i][x] = f[i][y] = (ll)(f[i][x] + f[i][y]) * inv2 % mod;
				f[x][i] = f[y][i] = (ll)(f[x][i] + f[y][i]) * inv2 % mod;
			}
		}
		f[x][y] = f[y][x] = (ll)(f[x][y] + f[y][x]) * inv2 % mod;
	}
	int sum = 0;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			sum = (sum + f[i][j]) % mod;
	ans = (ll)sum * ans % mod;
	printf("%d\n", ans);
}
//

Measured memory_bytes: 35584
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

const int MAX = 107;
const int MOD = 1000000007;

void solve() {
    int x, n;
    cin >> x >> n;
    int p[MAX];
    bool ok = true;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        if (p[i] == x) {ok = false;}
    }
    if (ok) {cout << x; return;}
    sort(p, p + n);
    for (int i = 1; i <= INT_MAX; i++) {
        bool okS = true, okL = true;
        for (int j = 0; j < n; j++) {
            if (x-i == p[j]) {
                okS = false;
            }
            else if (x+i == p[j]) {
                okL = false;
            }
        }
        if (okS) {
            cout << x-i; return;
        }
        else if (okL) {
            cout << x+i; return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve(); cout << endl;}
    solve();
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>

using namespace std;

long long f(int n, long long c, vector<long long>& xs, vector<long long>& vs){
    vector<long long> cost1(n+1);
    long long acc=0;
    for(int i=0; i<n; ++i){
        acc+=vs[i];
        cost1[i+1]=acc-xs[i];
    }
    vector<long long> cost2(n+1);
    acc=0;
    for(int i=n-1; i>=0; --i){
        acc+=vs[i];
        cost2[i+1]=max(cost2[(i+2)%(n+1)], acc-(c-xs[i])*2);
    }
    long long ans=0;
    for(int i=1; i<=n; ++i){
        ans=max(ans, cost1[i]+cost2[(i+1)%(n+1)]);
    }
    return ans;
}

int main(){
    int n; cin >> n;
    long long c; cin >> c;
    vector<long long> xs(n), vs(n);
    for(int i=0; i<n; ++i){
        cin >> xs[i] >> vs[i];
    }
    long long ans=f(n, c, xs, vs);
    reverse(xs.begin(), xs.end());
    for(int i=0; i<n; ++i){
        xs[i]=c-xs[i];
    }
    reverse(vs.begin(), vs.end());
    ans=max(ans, f(n, c, xs, vs));
    cout << ans << endl;
    return 0;
}


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

using namespace std;

struct Query {
  int T;
  int F;
  char C;
};

int main()
{
  string S;
  int Q;
  vector<Query> query;

  cin >> S >> Q;

  query.resize(Q);
  for (int i = 0; i < Q; i++) {
    cin >> query[i].T;
    if (query[i].T == 2) {
      cin >> query[i].F;
      cin >> query[i].C;
    }
  }

  deque<char> d;
  for (auto &&i : S) {
    d.push_back(i);
  }

  bool f = false;

  for (int i = 0; i < Q; i++) {
    if (query[i].T == 1) {
      f = !f;
    }
    else if ((query[i].F == 1 && !f) || (query[i].F == 2 && f)) {
      d.push_front(query[i].C);
    }
    else {
      d.push_back(query[i].C);
    }
  }

  if (f) {
    reverse(d.begin(), d.end());
  }

  for (auto &&i : d) {
    cout << i;
  }

  return 0;
}


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

const int MAX = 100;
int main() {
	int N, A[MAX], A2[MAX];
	cin >> N;
	for (int i = 0;i < N;i ++) cin >> A[i];
	for (int i = 0;i < N;i ++) cin >> A2[i];
	int max = 0, sum;
	for (int i = 1;i < N;i ++) {
		A[i] += A[i - 1]; // 累積和
	}
	for (int i = N - 2;i >= 0;i --) {
		A2[i] += A2[i + 1]; // 同じく
	}
	for (int i = 0;i < N;i ++) { // i番目で下へ降りる
		sum = A[i] + A2[i];
//		cout << i << ":(" << A[i] << "," << A2[i] << ")" << endl;
		if (sum > max) max = sum;
	}
	cout << max;
	return 0;
}

Measured memory_bytes: 256
A = []

for i in range(3):
    bingo_line = input().split()
    for j in range(3):
        A.append(int(bingo_line[j]))

N = int(input())

side = [0,0,0]
vertical = [0,0,0]


for i in range(N):
    number = int(input())
    if number in A:
        xy = A.index(number)
        y = xy // 3
        x = xy % 3
        vertical[y] += 1
        side[x] += 1
        A[xy] = 0

if 3 in side:
    print('Yes')
    exit();
if 3 in vertical:
    print('Yes')
    exit();
if A[4]==0 and A[0]==0 and A[8]==0:
    print('Yes')
    exit();
elif A[4]==0 and A[2]==0 and A[6]==0:
    print('Yes')
    exit();
    
print('No')

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int Int() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Int() + add;
        }
        return Array;
    }

    public long Long() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Long() + add;
        }
        return Array;
    }
}
class Program {
    static Scanner cin = new Scanner();
    static void Main() {
        int N = cin.Int();
        var L = cin.ArrayInt(N);
        
        Array.Sort(L);
        int sum = L.Sum() - L[N - 1];
        Console.WriteLine(L[N - 1] - sum < 0 ? "Yes" : "No");
        Console.ReadLine();
    }
}

Measured memory_bytes: 13268
#include <iostream>
#include <string>
#include <set>
using namespace std;

int main(){
    int N, K;
    cin >> N >>K;
    int d, a;
    set<int> snuke;
    for (int i = 0; i < K; i++){
        cin >> d;
        for (int j = 0; j < d; j++){
            cin >> a;
            snuke.insert(a);
        }
    }
    int ans = N - snuke.size();
    cout << ans << endl;
}




Measured memory_bytes: 3632
n, m = map(int, input().split())
rednow = [-1, 1] + [0 for i in range(n-1)] # maybe there's red ball
balnum = [-1] + [1 for i in range(n)] # the number of ball, each box
order = []
for i in range(m):
  order.append(list(map(int, input().split()))) 

for q in order:
  if rednow[q[0]] == 1:
    rednow[q[1]] = 1
    if balnum[q[0]] == 1:
      rednow[q[0]] = 0
  balnum[q[0]] -= 1
  balnum[q[1]] += 1

print(rednow.count(1))


Measured memory_bytes: 28880
#include <iostream>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <bitset>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <deque>
#include <ctime>
#define s(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define ss(n) scanf("%s",n)
#define s2(a,b) scanf("%d%d",&a,&b)
#define SET(p)      memset(p,-1,sizeof(p))
#define CLR(p)      memset(p,0,sizeof(p))
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LL long long
#define ULL unsigned long long
#define R freopen("in","r",stdin)
#define W freopen("out","w",stdout)
using namespace std;

vector<vector<int> > arr;
vector<vector<int> > hor;
vector<vector<int> > ver;

int main() {
	int n,m,q;
	cin>>n>>m>>q;

	arr.resize(n,vector<int>(m,0));
	hor.resize(n,vector<int>(m,0));
	ver.resize(n,vector<int>(m,0));
	
	char str[m+1];
	for(int i=0;i<n;i++){
		ss(str);
		for(int j=0;j<m;j++){
			arr[i][j]=(int)(str[j] - '0');
			if(j>0){
				hor[i][j] += (arr[i][j]&&arr[i][j-1]);
			}
			if(i>0){
				ver[i][j] += (arr[i][j]&&arr[i-1][j]);
			}
		}
	}
	
	for(int i=0;i<n;i++) {
		for(int j=1;j<m;j++){
			arr[i][j] += (arr[i][j-1]);
			hor[i][j] += (hor[i][j-1]);
			ver[i][j] += (ver[i][j-1]);
		}
	}

	for(int i=1;i<n;i++) {
		for(int j=0;j<m;j++){
			arr[i][j] += (arr[i-1][j]);
			hor[i][j] += (hor[i-1][j]);
			ver[i][j] += (ver[i-1][j]);
		}
	}

	// for(int i=0;i<n;i++){
	// 	for (int j=0;j<m;j++){
	// 		cout<<arr[i][j]<<" ";

	// 	}
	// 	cout<<endl;
	// }
	// cout<<endl;
	// for(int i=0;i<n;i++){
	// 	for (int j=0;j<m;j++){
	// 		cout<<hor[i][j]<<" ";

	// 	}
	// 	cout<<endl;
	// }
	// cout<<endl;

	// for(int i=0;i<n;i++){
	// 	for (int j=0;j<m;j++){
	// 		cout<<ver[i][j]<<" ";

	// 	}
	// 	cout<<endl;
	// }
	// cout<<endl;


	int x1,x2,y1,y2;
	for(int i=0;i<q;i++){
		int ans = 0;
		s2(x1,y1);
		s2(x2,y2);
		x1--;y1--;x2--;y2--;

		ans += arr[x2][y2];
		if(x1 > 0){
			ans -= arr[x1-1][y2];
		}
		if(y1 > 0){
			ans -= arr[x2][y1-1];
		}
		if(x1>0 && y1>0) {
			ans += arr[x1-1][y1-1];
		}

		// cout<<ans<<endl;

		y1++;
		if(y2>=y1){
			ans -= hor[x2][y2];
			if(x1 > 0){
				ans += hor[x1-1][y2];
			}
			if(y1 > 0){
				ans += hor[x2][y1-1];
			}
			if(x1>0 && y1>0) {
				ans -= hor[x1-1][y1-1];
			}
		}
		y1--;

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

		x1++;
		// cout<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<endl;
		if(x2>=x1){
			ans -= ver[x2][y2];
			// cout<<ver[x2][y2];
			if(x1 > 0){
				ans += ver[x1-1][y2];
				// cout<<ver[x1-1][y2];
			}
			if(y1 > 0){
				ans += ver[x2][y1-1];
				// cout<<ver[x2][y1-1];
			}
			if(x1>0 && y1>0) {
				ans -= ver[x1-1][y1-1];
				// cout<<ver[x1-1][y1-1];
			}
		}
		printf("%d\n", ans);
	}
	
}

Measured memory_bytes: 49664
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <string>
using namespace std;
int main(void){
  int x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;
  string root;
  for(int i=0; i<x2-x1; i++){
    cout<<"R";
    root+="R";
  }
  for(int i=0; i<y2-y1; i++){
    cout<<"U";
    root+="U";
  }
  cout<<"R";
  root+="R";
  for(int i=0; i<y2-y1+1; i++){
    cout<<"D";
    root+="D";
  }
  for(int i=0; i<x2-x1+1; i++){
    cout<<"L";
    root+="L";
  }
  cout<<"U";
  root+="U";

    for(int i=0; i<y2-y1; i++){
    cout<<"U";
    root+="U";
  }
  for(int i=0; i<x2-x1; i++){
    cout<<"R";
    root+="R";
  }
  cout<<"U";
  root+="U";
  for(int i=0; i<x2-x1+1; i++){
    cout<<"L";
    root+="L";
  }
  for(int i=0; i<y2-y1+1; i++){
    cout<<"D";
    root+="D";
  }
  cout<<"R";
  root+="R";
  cout<<endl;
}

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

typedef long long ll;

int main(){
    string s;
    cin >> s;

    ll ans = 0;
    int b = 0;

    for(int i = 0; i < s.length(); i++){
        if(s[i] == 'B') b++;
        else            ans += b;
    }

    cout << ans << endl;
    
    return 0;
}

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

int main() {
  int a, b, x;
  
  cin >> a;
  cin >> b;
  
  if ((a * b) % 2 == 0 ) {
    cout << "Even" << endl;
  } else {
    cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
def main():
    N = int(input())
    A = list(map(int, input().split()))
    AA = [(a, i) for i, a in enumerate(A)]
    AA.sort(reverse=True)
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        a, t = AA[i]
        for x in range(i + 2):
            y = i + 1 - x
            dp[x][y] = max((dp[x - 1][y] + abs(t - (x - 1)) * a) if x > 0 else 0,
                           (dp[x][y - 1] + abs(t - (N - y)) * a) if y > 0 else 0)
    return max(dp[i][N - i] for i in range(N + 1))

print(main())


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

int main(){
  int h,w;
  while(cin >> h >> w){
    vector<vector<char>> vv;
    //vector<vector<int>> ans;
  
    for(int i=0; i<h; ++i){
      vector<char> v;
      for(int j=0; j<w; ++j){
	char tmp;
	cin >> tmp;
	v.push_back(tmp);
      }
      vv.push_back(v);
    }

    for(int i=0; i<h; ++i){
      for(int j=0; j<w; ++j){
	int ans = -1;
	for(int k=j; k>=0; --k){
	  if(vv[i][k] == 'c'){
	    ans = j-k;
	    break;
	  }
	}
	if(j!=w-1){
	  cout << ans << " ";
	}else{
	  cout << ans;
	}
      }
      cout << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3172
import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
l=len(format(A.max(),'b'))
MOD=10**9+7

tei=1
ans=0
for i in range(l):
  B=(A >> i) & 1
  one=np.count_nonzero(B)
  zero=N-one
  ans+=tei*one*zero
  tei*=2
print(ans%MOD)

Measured memory_bytes: 49928
#include<bits/stdc++.h>
#define mod 1000000007

using namespace std;

int main() {
    int n;
    cin>>n;
    long long int a[n];
    long long int sum = 0;
    for(int i = 0; i < n; i++) {
        cin>>a[i];
        sum += a[i]%mod;
    }
    sum %= mod;
    long long int ans = 0;
    for(int i = 0; i < n; i++) {
        sum = (sum+mod-a[i]%mod)%mod;
        ans += (a[i]%mod * sum)%mod;
    }
    cout<<ans%mod<<endl;
    return 0;
}

Measured memory_bytes: 5140
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	string a, c;
	int b = 0;
	cin >> a ;
	for(int i=0;i<4;i++){
		for (int j = 0; j < 4; j++) {
			if (a[i] == a[j]) { b++; }
		}
	}
	if (b == 8) { c = "Yes"; }
	else { c = "No"; }
	cout << c << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int n, max_i=0;
  cin >> n;
  long long a[n];
  long long max_a=0, max_tmp=0;
  for (int i = 0; i < n; i++){
    cin >> a[i];
    if (max_a <= a[i]){
      max_a = a[i];
      max_i = i;
    }
  }

  int max_j=0;

  for (int i = 0; i < n; i++){
    if (i != max_i) {
      long long tmp = a[i] * (max_a - a[i]);
      if (max_tmp <= tmp){
        max_tmp = tmp;
        max_j = i;
      }
    }
  }
  
  printf("%lld %lld\n",a[max_i], a[max_j]);
  
}


Measured memory_bytes: 4444
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
 
using namespace std;
 
#define pai 3.14159265359
#define mod 1000000007

int main()
{
    int n;
    cin >> n;
    int a[100001], b[100001];
    for(int i = 0; i < n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b, b + n);
    map<int, int> num;
    for(int i = 0; i < n; i++){
        num[b[i]] = i % 2;
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(i % 2 != num[a[i]]) ans++;
    }
    cout << ans / 2 << endl;
    return 0;
}

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


//defines...
#define ll long long
#define tata return;
#define pb push_back
#define mp make_pair
#define in insert
#define run ios_base::sync_with_stdio(false);cin.tie(NULL);
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define vec vector<ll>
#define setl set<ll>
#define mapl map<ll,ll>
#define shunno cout<<0<<endl;
#define pi 2*acos(0.0)1
#define hobena cout<<-1<<endl;







void oka()
{
    ll a,b;
    cin>>a>>b;
    multimap<string,string>m;
    while(a--)
    {
        string s;
        cin>>s;
        m.insert(pair<string,string>(s,s));
    }
    multimap<string,string>::iterator it;
    for(it=m.begin();it!=m.end();it++)
        cout<<it->second;
    cout<<endl;




}






int main()
{

   //string g="abcd";
    //g.erase(g.begin()+3);
    //cout<<g<<endl;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    run
    ll i,t;
    t=1;
  // cin>>t;


    for(i=1;i<=t;i++)
    {


    oka();
    }






}

Measured memory_bytes: 3668
import sys
import numpy as np
N, K = [int(x) for x in input().split()]
x = np.array([int(x) for x in input().split()])
if 0 in x:
    K -= 1
x = x[np.nonzero(x)]
if K == 0:
    print(0)
    sys.exit()
ans = []
for i in range(len(x)-K+1):
    if (x[i] < 0) != (x[i+K-1] < 0):
        ans.append(abs(x[i])+abs(x[i+K-1])+min(abs(x[i]),abs(x[i+K-1])))
    else:
        ans.append(max(abs(x[i]),abs(x[i+K-1])))
print(min(ans))

Measured memory_bytes: 23072
S = []
H = []
C = []
D = []

n = int(input())
for i in range(n):
    mark, num = [x for x in input().split()]
    if mark == 'S':
        S.append(int(num))

    elif mark == 'H':
        H.append(int(num))

    elif mark == "C":
        C.append(int(num))

    else: #D
        D.append(int(num))


for i in range(1,14):
    if not i in S:
        print("S", i)
for i in range(1,14):
    if not i in H:
        print("H", i)
for i in range(1,14):
    if not i in C:
        print("C", i)
for i in range(1,14):
    if not i in D:
        print("D", i)

Measured memory_bytes: 7708
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;

template<class T,class U>constexpr bool chmin(T&a,const U b){if(a<=b)return false;a=b;return true;}
template<class T,class U>constexpr bool chmax(T&a,const U b){if(a>=b)return false;a=b;return true;}
#define bit(n,k) ( (n>>k)&1 )

//デバッグ
template<class T>
void Vout(vector<T> &V){
    cout<<"\nstart\n";
    const int sz=V.size();
    for(int i=0;i<sz;i++){
        cout<<i<<" "<<V[i]<<'\n';
    }
    cout<<"end\n"<<endl;
}

template<class T>
void VPout(vector<T> &V){
    cout<<"\nstart\n";
    const int sz=V.size();
    for(int i=0;i<sz;i++){
        cout<<i<<" "<<V[i].first<<" "<<V[i].second<<'\n';
    }
    cout<<"end\n"<<endl;
}


//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


constexpr int MAX=1<<30;
constexpr ll INF=1LL<<62;
constexpr int MOD=1e9+7;
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};

//__builtin_popcount(S);
//#define int ll
//vector<vector<int>> data(3, vector<int>(4));
//vector.resize(a,vector<int>(b,-1));
//vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3, 初期値)));


//辺 fromあり
template<typename T >
struct Edge {
  int from, to;
  T cost;

  Edge()=default;
  Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}

};

template<typename T>
using Edges=vector<Edge<T>>;


template<typename T>
vector<T> BellmanFord(const Edges<T> &g,const int v,const int s,const T inf,const T _inf,const T zero){
    vector<T> dist(v,inf);
    dist[s]=zero;
    for(int i=0;i<v-1;i++){ //v-1回のループ 不閉路を気にしない場合はここだけ
        for(auto &e:g){
            if(dist[e.from]==inf) continue;
            chmin(dist[e.to],dist[e.from]+e.cost); //Tの足し算、比較
        }
    }
    //不閉路の有無だけを気にする場合はこれを利用
    //不閉路がある場合は空を返す
    /*for(auto &e:g){
        if(dist[e.from]==inf) continue;
        if(dist[e.from]+e.cost<dist[e.to]) return vector<T>();
    }
    return dist;
    */
    
    //負の無限大になるところを調べる _infにする
    for(int i=0;i<v-1;i++){
        for(auto &e:g){
            if(dist[e.from]==inf) continue;
            if(dist[e.from]+e.cost<dist[e.to]) dist[e.to]=_inf; //_infを使用
        }
    }
    return dist;
} 


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    cout<<fixed<<setprecision(10);

    int n,m,p;
    cin>>n>>m>>p;
    Edges<ll> g;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        a--; b--;
        c=p-c;
        g.emplace_back(a,b,c);
    }
    auto ans=BellmanFord<ll>(g,n,0,INF,-INF,0);
    if(ans[n-1]==-INF) cout<<-1<<endl;
    else cout<<max(-ans[n-1],0LL)<<endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using P = std::pair<int,int>;

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

        std::vector<int> ans(0);
        for(int i=n; i>0;){
                for(int j=std::max(0,i-m); j<=i; j++){
                        if(j==i){
                                puts("-1");
                                return 0;
                        }
                        if(s[j]=='0'){
                                ans.push_back(i-j);
                                i = j;
                                break;
                        }
                }
        }

        for(int i=ans.size()-1; i>=0; i--) printf("%d ", ans[i]);
        puts("");
        return 0;
}


Measured memory_bytes: 1020
#include<iostream>

using namespace std;

const int N=100004;

int BIT[N];

void add(int x,int y){
	if(x>N)return;
	BIT[x]+=y;
	add(x+(x&-x),y);
}
int sum(int i){
	if(!i)return 0;
	return BIT[i]+sum(i-(i&-i));
}

int main(){
	int n,q;
	cin>>n>>q;
	for(int i=0;i<q;i++){
		int c,x,y;
		cin>>c>>x>>y;
		if(c==0){
			add(x,y);
		}else{
			if(x>y)swap(x,y);
			cout<<sum(y)-sum(x-1)<<endl;
		}
	}
}

Measured memory_bytes: 1548
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
  ll n;
  cin >> n;
  
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  ll sum = a[0];
  rep(i, n - 1) sum ^= a[i + 1];
  rep(i, n) { 
    ll res = sum ^ a[i];
    cout << res << " ";
   }
   cout  << endl;
  return 0;
}

Measured memory_bytes: 4684
import java.lang.Math.*

fun main(args: Array<String>) {
    val s = readLine()!!
    val t = readLine()!!

    val dp = Array(s.length + 1) { IntArray(t.length + 1) }

    for (i in s.indices){
        for (j in t.indices){
            if(s[i] == t[j]){
                dp[i + 1][j + 1] = dp[i][j] + 1
            }else{
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
            }
        }
    }

    var x = s.length
    var y = t.length
    var ans = ""
    while (x > 0 && y > 0){
        when {
            dp[x][y] == dp[x][y - 1] -> {
                y--
            }
            dp[x][y] == dp[x - 1][y] -> {
                x--
            }
            else -> {
                ans += s[x - 1]
                x--
                y--
            }
        }
    }
    if (ans.isNotBlank()) println(ans.reversed())
}

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

int main()
{
    string s;
    int a[26]={0};
    cin>>s;
    for (size_t i = 0; i < s.length(); i++)
    {
        a[s[i] - 'a'] += 1;
    }
    for (size_t i = 0; i < 26; i++)
    {
        if(a[i]>1){
            cout << "no" << endl;
            return 0;
        }
    }
    cout << "yes" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
typedef long long ll;
int main() {
    int N;
    cin >> N;
    vector<int>L(N);
    rep(i, 0, N){
        cin >> L[i];
    }
    sort(L.begin(), L.end());
    int ans = 0;
    rep(b, 0, N){
        rep(a, 0, b){
            
            int ab = L[a]+L[b];
            
            int r = lower_bound(L.begin(), L.end(), ab) - L.begin();
           
            int l = b+1;
           
            ans += max(0,r-l);
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main(void){
   int a,b,c;
   cin>>a>>b>>c;
   if(a==b+c||b==a+c||c==a+b){
      cout<<"Yes"<<endl;
   }else{
      cout<<"No"<<endl;
   }
   return 0;
}



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

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    s = " " + s;
    string repr(2 * n + 1,' ');
    for(int i = 1;i <= 2 * n;i++){
        repr[i] = '0' + ((s[i] == 'B') == (2 * n - i + 1) % 2);
    }
    
    int ans = 1;
    int cnt0 = 0;

    for(int i = 1;i <= 2 * n;i++){
        if(repr[i] == '0'){
            cnt0++;
        }
        else{
            if(cnt0 <= 0){
                ans = 0;
                break;
            }
            ans = 1LL * ans * cnt0 % MOD;
            cnt0--;
        }
    }

    if(cnt0 > 0){
        ans = 0;
    }

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

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 772
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	mod = 10^9+7
	n = readline() |> parseInt
	a = readline() |> split |> parseMap
	if a[1] != 0
		println(0)
	else
	dp = zeros(Int,n)
	dp[1] = 1
	r = 1
	g = 0
	b = 0
	for i in 2:n
		k = 0
		f = 0
		if a[i]==r
			r += 1
			f = 1
			k += 1
		end
		if a[i]==g
			if f == 0
				g += 1
				f += 1
			end
			k += 1
		end
		if a[i]==b
			if f == 0
				b += 1
				f += 1
			end
			k += 1
		end
		dp[i] = (dp[i-1]*k)%mod
	end
	dp[n] = (dp[n]*3)%mod
	println(dp[n])
end
end

main()

Measured memory_bytes: 171168
'''input
13 1 4 3000
'''

R, G, B, N=map(int, input().split())

count=0
for r in range(N//R+1):
	for g in range((N-R*r)//G+1):
		# b=
		if (N-R*r-G*g)%B==0: 
			# print(r, g, b)
			count+=1

print(count)


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

int main() {
    int n, m;
    cin >> n >> m;
    unordered_set<int> score;
    vector<int> p(m);
    vector<string> s(m);
    vector<int> pen(n + 1, 0);
    rep(i, m) {
        cin >> p[i] >> s[i];
        if (s[i] == "AC") {
            score.insert(p[i]);
        } else if (!score.count(p[i])) {
            pen[p[i]]++;
        }
    }
    int pensum = 0;
    for (int i = 1; i <= n; i++) {
        if (score.count(i)) {
            pensum += pen[i];
        }
    }
    printf("%d %d\n", (int)score.size(), pensum);
}

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

using namespace std;

typedef long long ll;
#define fi first
#define se second
#define pb push_back

const int N = 20;
vector <pair <int, int> > v[N];
bool is[N], vis[N], ans;

void dfs(int x) {
    vis[x] = true;
    if (!is[x]) return;
    for (auto y : v[x]) {
        if (y.se != is[y.fi]) ans = false;
        if (!vis[y.fi]) {
            dfs(y.fi);
        }
    }
}

int main() {
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        while (a--) {
            int x, y;
            scanf("%d %d", &x, &y);
            v[i].pb({x - 1, y});
        }
    }
    int res = 0;
    for (int i = 0; i < (1 << n); i++) {
        int hold = 0;
        for (int j = 0; j < n; j++) {
            if ((1 << j) & i) {
                is[j] = true;
                hold++;
            } else {
                is[j] = false;
            }
            vis[j] = false;
        }
        ans = true;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                dfs(i);
            }
        }
        if (ans) {
            res = max(res, hold);
            //printf("%d\n", i);
        }
    }
    printf("%d", res);
    return 0;
}


Measured memory_bytes: 3828
let array_of_string s = Array.init (String.length s) (fun i -> s.[i])

let () =
  try
    read_line ()
    |> array_of_string
    |> (fun a ->
        Array.to_list (Array.init (Array.length a - 1) (fun i -> ((i + 1, i + 2), a.(i) = a.(i + 1)))) @
        Array.to_list (Array.init (Array.length a - 2) (fun i -> ((i + 1, i + 3), a.(i) = a.(i + 2)))))
    |> List.find (fun (_, b) -> b)
    |> (fun ((i, j), _) -> Printf.printf "%d %d\n" i j)
  with Not_found -> print_endline "-1 -1"

Measured memory_bytes: 23680
object Main extends App {
  val inputs = io.Source.stdin.getLines.toIndexedSeq
  .tail.map('.' +: _.toIndexedSeq :+ '.')
  val wall = inputs(0).map(_ => '.')
  val field = wall +: inputs :+ wall
  
  private def eval(x:Int, y:Int):Boolean={
    if(field(y)(x) != '#') return true
    if(field(y)(x-1) == '#') return true
    if(field(y)(x+1) == '#') return true
    if(field(y-1)(x) == '#') return true
    if(field(y+1)(x) == '#') return true
    //println(x,y)
    return false
  }
  private def func():Boolean={
    (1 until field.size-1 ).foreach{ y =>
      (1 until field(0).size-1 ).foreach{ x =>
        if(!eval(x,y)) return false
      }
    }
    return true
  }
  val ret = if(func()) "Yes" else "No"
  println(ret)
}


Measured memory_bytes: 27220
#include<iostream>
using namespace std;
int m,d,k,sum;
int main()
{
	cin>>m>>d;
	for(int i=1;i<=m;++i)
	{
		for(int j=2;j*j<=i&&j<=9;++j)
		{
			k=i/j;
			if(k*j==i&&k>=2&&k<=9)
			{
				if(j*10+k<=d) sum++;
				if(k*10+j<=d) sum++;
				if(j*10+k<=d&&j==k) sum--;
			}
		}
	}
	cout<<sum;
}

Measured memory_bytes: 256
N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
if M == 1:
  print(0)
else:
  if last > N:
    print(sum(ls_mod[:N]))
  else:
    shou = (N-fast) // diff
    amari = (N-fast) % diff
    print(sum(ls_mod[:fast])+sum(ls_mod[fast:])*shou+sum(ls_mod[fast:fast+amari]))



Measured memory_bytes: 13572
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <complex>
#include <tuple>

#define FAST ios_base::sync_with_stdio(false); cin.tie(0)
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define repr(i, a, b) for(int i=int(a); i>=int(b); i--)
#define reps(i,n) for(int i=1;i<=int(n);++i)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define iceil(x,y) (x+y-1)/y
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define all(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define LF "\n"

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

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

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII> PP;

long N,M,C;
long B[20];
long A[20];

int main()
{
	FAST;
	int ans=0;
	cin >> N >> M >> C;
	rep(i,M) cin >> B[i];
	rep(i,N) {
		rep(j,M) cin >> A[j];
		long t=0;
		rep(j,M) {
			t += (A[j]*B[j]);
			// cout << "A = " <<A[i] << LF;
			// cout << "B = " <<B[i] << LF;
		}
		t+=C;
		// cout << "t=" <<t << "\n";
		if (t>0) ans++;
	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
def totalprice_with_discount_ticket(ref, mic, discount_ticket):
    totalprice = min(ref) + min(mic)
    for t in discount_ticket:
        discnt_ref_num = t[0] - 1
        discnt_mic_num = t[1] - 1
        discnt_amt = t[2]
        if totalprice > ref[discnt_ref_num] + mic[discnt_mic_num] - discnt_amt:
            totalprice = ref[discnt_ref_num] + mic[discnt_mic_num] - discnt_amt

    return totalprice


if __name__ == '__main__':
    ref_num, mic_num, ticket_num = map(int, input().split())
    ref_list = list(map(int, input().split()))
    mic_list = list(map(int, input().split()))
    discount_ticket_list = [list(map(int, input().split()))
                            for i in range(ticket_num)]
    print(totalprice_with_discount_ticket(
        ref_list, mic_list, discount_ticket_list))

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

int main(){
  int n,k;
  int min=1;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    if(min*2<min+k)
      min*=2;
    else
      min+=k;
  }
  cout<<min<<'\n';
  return 0;
}


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

int main() {
  int A, B, C, D;
  
  cin >> A >> B >> C >> D;

  if ((A + B) == (C + D)) {
    cout << "Balanced" << endl;
  } else if ((A + B) > (C + D)) { 
    cout << "Left" << endl;
  } else { 
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
N=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        bw=4*i*j-N*i-N*j
        if bw<=0:
            continue
        if (N*i*j)%bw==0:
            print(i,j,(N*i*j)//bw)
            exit()

Measured memory_bytes: 40540
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main() {
	ll a, b;
	cin >> a >> b;
	ll ans = 0,flag = 0;
	while (a != 1) {
		for (ll i = 2; i <= sqrt(a); i++) {
			if (a % i == 0) {
				a /= i;
				if (b % i == 0)ans++;
				while (a % i == 0)a /= i;
				flag = 1;
				break;
			}
		}
		if (flag == 0) {
			if (b % a == 0)ans++;
			break;
		}
		flag = 0;
	}
	cout << ans + 1;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <iomanip>

typedef long double ld;
typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

// Split
namespace util {

std::vector< std::string > split(std::string s, char delimiter)
{
  std::vector< std::string > vs;
  std::string sub;
  for (auto c : s) {
    if (c == delimiter) vs.push_back(sub), sub.clear();
    else sub += c;
  }
  vs.push_back(sub);
  return vs;
}

} // namespace util

// Minimum, Maximum
template<class T> T minimum(T head, T tail) { return std::min(head, tail); }
template<class H, class... T> H minimum(H head, T... tail) { return std::min(head, minimum(tail...)); }
template<class T> T maximum(T head, T tail) { return std::max(head, tail); }
template<class H, class... T> H maximum(H head, T... tail) { return std::max(head, maximum(tail...)); }

// Output
template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  for (ll i = 0; i < (ll)v.size(); i++){ os << " [" << i << "]" << v[i]; if (i % 10 == 0) os << std::endl; }
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::vector< std::pair<T, S> > vp)
{
  ll i = 0;
  for (auto p : vp){os << " [" << i++ << "]" << p.first << " " << p.second; if (i % 10 == 0) os << std::endl;}
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

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

  ll A, B, K;
  std::cin >> A >> B >> K;

  std::map<ll, ll> mn;
  ll cnt = 0LL;
  for (ll i = A; cnt < K && i <= B; i++) {
    mn[i]++;
    cnt++;
  }

  cnt = 0LL;
  for (ll i = B; cnt < K && i >= A; i--) {
    mn[i]++;
    cnt++;
  }

  std::vector<ll> vans;
  for (auto p : mn) {
    vans.push_back(p.first);
  }
  std::sort(vans.begin(), vans.end());

  for (auto x : vans) {
    print(x);
  }

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	vector<int> ans;
	int a;
	float b,c;
	while(scanf("%d,%f,%f",&a,&b,&c) != EOF){
		if((b/(c*c)) >= 25){
			ans.push_back(a);
		}
	}
	for(int i=0; i<ans.size(); i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 1248
#include <bits/stdc++.h>
#define drep(i,cc,n) for(int i=(cc);i<=(n);++i)
#define rep(i,n) drep(i,0,(n)-1)
#define drrep(i,cc,n) for(int i=(cc);i>=(n);--i)
#define rrep(i,n) drrep(i,0,(n)-1)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,v.size())if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define arrprint(v,n) rep(i,n)if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define matprint(v,n,m) rep(i,n){rep(j,m){cout << v[i][j] << " ";}cout << endl;}
#define SORT(v) sort(v.begin(), v.end())
#define REV(v) reverse(v.begin(), v.end())
using namespace std;
const int mod=1000000007;
const long long INF=-1001001001001;
using ll = long long;
using P = pair<int,int>;
template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; //小さいものから取り出す


int main(){
    int n,k;
    cin >> n >> k;
    vector<int> p(n),c(n);
    rep(i,n){cin >> p[i];p[i]--;}
    rep(i,n)cin >> c[i];
    vector<int> a[5000];
    set<int> s;
    int con = 0;
    rep(i,n){
        int now = i;
        if(s.find(now) != s.end())continue;
        a[con].push_back(now);
        s.insert(now);
        while(p[now] != a[con][0]){
            now = p[now];
            a[con].push_back(now);
            s.insert(now);
        }
        con++;
    }
    ll ans = INF;
    rep(i,con){
        ll tans = 0;
        int l = sz(a[i]);
        ll all = 0;
        rep(j,l) all += c[a[i][j]];
        int kk;
        if(all>0){
            if(k/l > 1){
                tans = all*(k/l-1);
                kk  = k%l+l;
            }else{
                kk = k;
            }
        }else{
            kk = min(k,l);
        }
        ll ttans = INF;
        rep(j1,l){
            ll tans2 = 0;
            rep(jj,kk){
                int j2 = (j1+jj)%l;
                tans2 += c[a[i][j2]];
                ttans = max(ttans,tans2);
                // if(i == 1)cout << jj << " " << tans2 << endl;;
            }
        }
        tans += ttans;
        // cout << i << " " << l << " " << tans << " " << kk << " " << all << endl;
        ans = max(ans,tans);
    }
    // cout << con << endl;

    cout << ans << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 4064
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    if(a==b&&b==c&&c==a||a!=b&&b!=c&&c!=a)
    {
        cout<<"No"<<endl;
    }
   else
    {
        cout<<"Yes"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <utility>
#include <set>
using namespace std;
typedef long long ll;


int main()
{
  ll n,cap;
  cin>> n >> cap;
  int w[n],v[n];
  for(ll i=0;i<n;i++) cin >> w[i]>>v[i];
  
  ll dp[n+1][cap+1];
  for(ll i=0;i<=n;i++){
    for(int j=0;j<=cap;j++){
      if(i==0 || j==0) dp[i][j]=0;
      else if(w[i-1]<=j) dp[i][j]=max(dp[i-1][j],v[i-1]+dp[i-1][j-w[i-1]]);
      else dp[i][j]=dp[i-1][j];
    }
  }
  cout<<dp[n][cap];
}

Measured memory_bytes: 79104
#include<stdio.h>

int insertionSort(int A[],int n, int g){
	
	int i,j,t;
	int v,count;
	
	count=0;
	
	for(i=g; i<n; i++){
		
		v=A[i];
		j=i-g;
		
		while (j >= 0 && A[j] > v){
			A[j+g] = A[j];
			j = j - g;
			count++;
			
		}
		A[j+g] = v;
	}
	
	return count;
}

	

void ShellSort(int A[], int n){
	
	int i,j,t,k,count;
	int G[100];
	G[0]=1;
	count=0;
	
	for(i=0; G[i]<=n; i++){
		G[i+1] = 3*G[i] + 1;
	}
	
	for(j=i-1; j>=0; j--){
		count = count + insertionSort(A,n,G[j]);
	}
	printf("%d\n",i);
	
	for(t=i-1; t>=0; t--){
		printf("%d",G[t]);
		if(t>0){
			printf(" ");
		}
		
	}
		
	printf("\n");
	printf("%d\n",count);
	for(k=0; k<n; k++){
		printf("%d",A[k]);
		
		if(k<n-1){
			printf("\n");
		}
	}
}



int main(void){
	
	int i,n;
	
	scanf("%d",&n);
	
	int A[n];
	
	for(i=0; i<n; i++){
		scanf("%d",&A[i]);
	}
	
	ShellSort(A, n);
	
	
	return 0;
}





Measured memory_bytes: 5656
#include<iostream>
#include<vector>
using namespace std;
vector<int>ans;
vector<int>G[1001];
int N,M;
vector<int>vis;
bool used[1001];
void dfs(int u)
{
	vis.push_back(u);
	used[u]=true;
	for(int v:G[u])
	{
		if(vis[0]==v)
		{
			if(ans.empty()||ans.size()>vis.size())ans=vis;
		}
		else if(!used[v])dfs(v);
	}
	vis.pop_back();
}
main()
{
	cin>>N>>M;
	for(int i=0;i<M;i++)
	{
		int u,v;cin>>u>>v;
		G[u].push_back(v);
	}
	for(int i=0;i++<N;)
	{
		for(int j=0;j++<N;)used[j]=false;
		dfs(i);
	}
	if(ans.empty())cout<<-1<<endl;
	else
	{
		cout<<ans.size()<<endl;
		for(int id:ans)cout<<id<<endl;
	}
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
using namespace std;

typedef long long ll;

int main() {
	string s; cin >> s;
	if (s[0] == s[1] && s[1] == s[2]) {
		cout << "Yes" << endl;
		return 0;
	}
	if (s[3] == s[1] && s[1] == s[2]) {
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 764
if __name__ == "__main__":
    S = input()

    for i in range(len(S)):
        if S[i] == 'R' and i % 2 == 1:
            print('No')
            exit()
        elif S[i] == 'L' and i % 2 == 0:
            print('No')
            exit()
    
    print('Yes')


Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {
	static long a = 1_000_000_007;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    int M = sc.nextInt();
	    sc.close();
	    
	    if (N-M>1 || N-M<-1)
	    	System.out.println(0);
	    
	    else {
	    	long ans = 1;
	    	for(int i = 1; i<=N; i++) {
	    		ans *= i;
	    		ans = ans % a;
	    	}
		
	    	for(int i = 1; i<=M; i++) {
	    		ans *= i;
	    		ans = ans % a;
	    	}
		
	    	if(N == M) {
	    		ans *= 2;
	    		ans = ans % a;
	    		System.out.println(ans);
	    	}
	    	else {
	    		System.out.println(ans);
	    	}
	    }
	}
}

Measured memory_bytes: 23764
#include <stdio.h>
long long fiboDP(int n){
    long long fibodp[200]={0};
    fibodp[1]=1;
    fibodp[2]=1;
    for(int i=3;i<=n;i++){
        fibodp[i]=fibodp[i-1]+fibodp[i-2];
    }
    return fibodp[n];
}
int main(void){
    int n;
    scanf("%d",&n);
    printf("%lld\n",fiboDP(n+1));
   return 0;
}


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

int main()
{
    int D;
    cin >> D;
    int c[26];
    int sd[D][26];
    for (int i = 0; i < 26; i++)
        cin >> c[i];
    for (int i = 0; i < D; i++)
    {
        for (int k = 0; k < 26; k++)
        {
            cin >> sd[i][k];
        }
    }
    int ans[D];
    ans[0] = 0;
    int select = 0;
    int tmp = 0;
    for (int i = 0; i < D; i++)
    {
        for (int k = 0; k < 26; k++)
            if (tmp != max(tmp, sd[i][k]))
            {
                tmp = max(tmp, sd[i][k]);
                select = k;
            }
        ans[i] = select + 1;
        tmp = 0;
    }
    for (int i = 0; i < D; i++)
        cout << ans[i] << endl;
}


Measured memory_bytes: 3656
MOD = 998244353
def main():
    N, M, K = (int(_) for _ in input().split())
    fact = [0] * (N + 1) # fact[n] = n!
    ifact = [0] * (N + 1)

    for i in range(N+1):
        if i == 0:
            fact[i] = 1
            continue
        fact[i] = i * fact[i-1]
        fact[i] %= MOD
    ifact[N] = pow(fact[N], MOD-2, MOD)
    for i in range(N)[::-1]:
        ifact[i] = ((i+1) * ifact[i+1])%MOD

    out = [0] * N
    coef = 1
    for i in range(N):
        out[N-1-i] = (coef * M * fact[N-1] * ifact[i] * ifact[N-1-i])%MOD
        coef *= M-1
        coef %= MOD
    ret = 0
    for i in range(K+1):
        ret += out[i]
        ret %= MOD
    print(ret)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 91272
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define srt(x) sort((x).begin(), (x).end());
#define rsrt(x) sort((x).rbegin(), (x).rend());
#define deb(x) cout<<#x<<" = "<<(x)<<" (L"<<LINE<<")"<<endl;
#define vdeb(x) {cout<<#x<<" = { "; rep(i, x.size()) cout<<x[i]<<' '; cout <<'}'<<" (L"<<LINE<<")"<<endl;}
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vivi = vector<vi>;
using vll = vector<long long>;
using vllvll = vector<vll>;
using vs = vector<string>;
using um = unordered_map<long long, long long>;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;

int main()
{
    ll A, B, H, M;
    cin >> A >> B >> H >> M;
    ld h, m;
    ld r = 2*M_PI;
    m = 2 * M_PI * (H*60 + M) / 60;
    h = m / 12;
    while (true) {
        ld tmp = h;
        tmp -= r;
        if (tmp < 0.0) break;
        h = tmp;
    }
    while (true) {
        ld tmp = m;
        tmp -= r;
        if (tmp < 0.0) break;
        m = tmp;
    }
    ld diff = abs(m - h);
    ld ans = A*A + B*B - 2*A*B*cos(diff);
    ans = sqrt(ans);
    printf("%.20Lf\n", ans);
}

Measured memory_bytes: 4100
#include<stdio.h>

int main(){
  
  int i,j,num,num2,count=0;
  int NUM[10001],NUM2[501];
  
  scanf("%d",&num);
  for(i=0;i<num;i++){
    scanf("%d",&NUM[i]);
    
  }
  
  scanf("%d",&num2);
  
  for(i=0;i<num2;i++){
    scanf("%d",&NUM2[i]);
    for(j=0;j<num;j++){
      
   
      
      if(NUM[j] == NUM2[i]){
	count++;
	break;
      }
    }
    
  }
  
  printf("%d\n",count);
  
  return 0;
}

Measured memory_bytes: 640
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
int dp[2000][2000] = {};
pair<int, int> input[2000] = {};
long long ans[20000] = {};
int main() {
	int n;
	cin >> n;
	REP(i, n + 1) {
		ans[i] = n + 1;
	}
	ans[0] = 0;
	REP(i, n) {
		cin >> input[i].first >> input[i].second;
	}
	queue<tuple<int,int, int>> hogea;
	REP(i, n) {
		hogea.push(make_tuple(i, i,input[i].second));
		dp[i][i] = 1;
	}
	while (hogea.empty() == false) {
		int left = get<0>(hogea.front());
		int right = get<1>(hogea.front());
		int heavy = get<2>(hogea.front());
		hogea.pop();
		if (left != 0) {
			if (input[left - 1].first >= heavy) {
				if (dp[left - 1][right] == 0) {
					dp[left - 1][right] = 1;
					hogea.push(make_tuple(left - 1, right, heavy + input[left - 1].second));
				}
			}
		}
		if (right != n - 1) {
			if (input[right + 1].first >= heavy) {
				if (dp[left][right + 1] == 0) {
					dp[left][right + 1] = 1;
					hogea.push(make_tuple(left, right + 1, heavy + input[right + 1].second));
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int q = i; q < n; ++q) {
			if (dp[i][q] == 1) {
				ans[q + 1] = min(ans[q + 1], ans[i] + 1);
			}
		}
	}
	cout << ans[n] << endl;
	return 0;
}


Measured memory_bytes: 7424
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
query = [(tuple(map(int, input().split()))) for _ in range(q)]

ans = 0
for A in combinations_with_replacement(range(1, m+1), n):
    point = 0
    for a, b, c, d in query:
        if A[b-1] - A[a-1] == c:
            point += d
    ans = max(point, ans)
print(ans)

Measured memory_bytes: 9004